(Basic Feasibility & Iterated Rounding) Suppose you are given a matrix A = {0, 1}*** such that each column of A has at most s ones, i.e., column sparsity is s. We want to find a coloring {-1, +1}" such that ||A|||||| is as small as possible. (a) Suppose we choose & uniformly at random, i.e., & is -1 or +1 with independently with equal probability. Show that in expectation ||Ae is O(n logn). Next, we will analyze the following polynomial time algorithm to find a coloring (-1, +1]" such that AlO(s), which is much better than O(n logn) when s is small. The algorithm will iteratively color more and more columns of A. Initially, all columns are "uncolored" and a column de gets "colored" when &t is defined. In any iteration, if the number of remaining uncolored columns is at most 2s, color them arbitrarily and halt. . Otherwise, we solve an LP with fractional variables denoting the fractional col- ors of the uncolored columns. For every row i that contains more than 28 un- colored ones, put an LP constraint that its fractional discrepancy is zero, i.e., a(i)Y = 0 where Y, denotes LP variable , -1,1] for uncolored columns t, and Y, denotes constant &, for colored columns t. Find a basic solution of the above LP, and for any uncolored column t that gets z {-1, +1} in this basic solution, we permanently set its e to that color. Repeat. (b) Show that in any iteration, the number of row constraints that we put is at most half the number of currently uncolored columns. Deduce that a basic solution will integrally color at least half the columns in each iteration. (c) Show that this algorithm obtains a solution with discrepancy O(s). This means, e.g., that if each column has O(1) non-zero entries then the discrepancy is O(1). Remark: There is nothing special about A = {0, 1] xn vs. A = [0, 1]x, i.e., having T n columns and real entries. We can easily extend the above result using the idea. of finding a basic solution in the beginning with at most n uncolored columns.