Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due
COS 521:Advanced Algorithms Homework 4
Instructions:
• Upload your solutions (to the non-extra-credit) to each problem as a separate PDF file (one PDF per problem) to codePost. Please make sure you are uploading the correct PDF! Please anonymize your submission (i.e., do not list your name in the PDF), but if you forget, it’s OK.
• If you choose to do extra credit, upload your solution to the extra credits as a single separate PDF file to codePost. Please again anonymize your submission.
• You may collaborate with any classmates, textbooks, the Internet, etc. Please upload a brief “collaboration statement” listing any collaborators as a separate PDF on codePost (if you forget, it’s OK). But always write up your solutions individually.
• For each problem, you should aim to keep your writeup below one page. For some problems, this may be infeasible, and for some problems you may write significantly less than a page. This is not a hard constraint, but part of the assignment is figuring out how to easily convince the grader of correctness, and to do so concisely. “One page” is just a guideline: if your solution is longer because you chose to use figures (or large margins, display math, etc.) that’s fine.
• Each problem is worth twenty points (even those with multiple subparts), unless explicitly stated otherwise.
Problems:
§1 This exercise is to remind you of some basic linear algebra.
(a) Show that every eigenvalue of a real symmetric matrix M ∈ R n×n is real. Hint: Use x TMx = x TMx for any n dimensional complex vector x.
(b) Show that any two eigenvectors corresponding to distinct eigenvalues of a real symmetric matrix M ∈ R n×n are orthogonal.
(c) Show that there exist n orthogonal eigenvectors of any real symmetric matrix M ∈ R n×n that span the entire n dimensional space.
(d) Using the previous part, show that the spectral norm of any matrix A ∈ R m×n , defined to be kAk2 := maxx kAxk2 kxk2 , is achieved when x is the eigenvector corresponding to the largest eigenvalue of AT A.
(e) Show that if the columns of a real square matrix M ∈ R n×n are orthonormal (i.e., have unit `2 norm and are pairwise orthogonal), then the rows of M are also orthonormal. (Hence, M is a unitary matrix.)
§2 This problem asks you to prove a bound on the spectral norm of random matrices which is valuable in analyzing many randomized algorithms.
Construct a random symmetric matrix R ∈ R n×n by setting Rij = Rji to +1 or −1, uniformly at random. Prove that, with high probability, kRk2 ≤ c p n log n,
for some constant c. This is much better than the naive bound of kRk2 ≤ kRkF = n.
Hint: For a symmetric matrix R, show that another way to write the spectral norm besides kRk2 := maxx kRxk2 kxk2 is that kRk2 = maxx |x T Rx| xT x .
Hint: Try to bound x T Rx xT x for one particular x, and then extend the result to hold for all x, simultaneously, by taking a -net for = 1 poly(n) from Lecture 12. It is possible to solve this problem using the standard Hoeffding bound for bounded random variables – so don’t use exotic concentration bounds!
§3 A matroid on [n] elements is a collection of sets that generalized the concept of linear independence for vectors. Specifically, a matroid I satisfies:
• Non-trivial: ∅ ∈ I.
• Downwards-closed: If S ∈ I, then T ∈ I for all T ⊆ S.
• Augmentation: If S, T ∈ I, and |S| > |T|, then there exists an i ∈ S \ T such that T ∪ {i} ∈ I.
(a) Prove that the following collections are matroids:
i. Sets of size at most k (that is, the elements are [n], and I = {X ⊆ [n]| |X| ≤ k}).
ii. Acyclic subgraphs of any undirected graph G = (V, E) (that is, the elements are E and I = {X ⊆ E|X contains no cycles}).
iii. Let G = (L, R, E) be a bipartite graph. The elements are L, and I = {X ⊆ L| |N(S)| ≥ |S| ∀S ⊆ X} (N(S) are the neighbors of S: {x ∈ R| ∃y ∈ S,(x, y) ∈ E}). That is, X ∈ I if and only if all nodes in X can be simultaneously matched to R.
(b) Given weights wi ≥ 0, i ∈ [n], and some collection of feasible sets I where ∅ ∈ I, your goal is to find the max-weight feasible set: arg maxS∈I{ P i∈S wi}. Consider a greedy algorithm that first sorts the elements in decreasing order of wi (i.e. picks a permutation σ such that wσ(i) ≥ wσ(i+1) for all i), then iteratively does the following (initializing A = ∅, i = 1, go until i > n): Check if A ∪ {σ(i)} ∈ I. If so, add σ(i) to A. Update i := i + 1. Prove that this greedy algorithm finds the max-weight feasible set no matter what non-negative weights are input if and only if I is a matroid (that is, prove that the algorithm succeeds whenever I is a matroid. Also, if I is not a matroid, provide an instance of weights for which the algorithm fails).
§4 In the submodular welfare problem, there are n bidders and m items. The value of bidder i ∈ {1, . . . n} for a subset of items S ⊆ {1, . . . , m} is given by a monotone submodular function fi(S) where fi(∅) = 0. We want to allocate the m items to the n bidders, i.e., find an item partition where bidder i gets susbset Si ⊆ {1, . . . , m} and Si ∩ Sj = ∅ for i 6= j, and the goal is to maximize the welfare P i∈{1,...,n} fi(Si). Show that the greedy algorithm which considers the items one-by-one in an arbitrary order and allocates the next item j to the bidder which has the highest marginal value (i.e., which maximizes fi(S ∪ j) − fi(S) where S is the currently allocated set of items to bidder i), gives a 2-approximation algorithm for the submodular welfare problem. Hint: Note that a submodular function remains submodular even if you “contract” a set, i.e., fS(A) := f(S ∪ A) − f(S) is also a submodular function on elements {1, . . . , m} \ S.
§5 (Discrepancy Theory) Suppose you are given a matrix A ∈ {0, 1} n×n such that each column of A has at most s ones, i.e., column sparsity is at most s. We will analyze the following polynomial time algorithm to find a coloring ~ε ∈ {−1, +1} n such that kA~εk∞ = k P t ~atεtk∞ = O(s), where ~at is the t-th column of A. The algorithm will iteratively color more and more columns of A. Initially, all columns are “uncolored” and a column ~at 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 colors of the uncolored columns. For every row i that contains more than 2s uncolored ones, put an LP constraint that its fractional discrepancy is zero, i.e., P t at(i)Yt = 0 where Yt denotes LP variable xt ∈ [−1, 1] for uncolored columns t, and Yt denotes constant εt for colored columns t.
• Find a basic solution x ∗ of the above LP, and for any uncolored column t that gets x ∗ t ∈ {−1, +1} in this basic solution, we permanently set its εt to that color.
• Repeat.
(a) Show that in any iteration, the number of row constraints that we put is at most half the number of currently uncolored columns. Thus a basic solution will integrally color many columns in each iteration.
(b) Show that this algorithm obtains a solution with discrepancy O(s).
Remark: There is nothing special about A ∈ {0, 1} n×n vs. A ∈ {0, 1} n×T , i.e., having T n columns. We can easily extend the above result to T columns using the idea of finding a basic solution in the beginning with at most n uncolored columns.
§6 (Online set cover): In the online set cover problem, we are given a universe U := {1, . . . , n} of n elements and a family S := {S1, . . . , Sm} of m sets where each S i Si = U. The algorithm starts with A = ∅ which denotes the collection of selected sets. In each time step t ∈ {1, . . . , T}, an adversary reveals an element et ∈ U, and the online algorithm has to immediately ensure that et ∈ S S∈A S, i.e., if et is already covered 4 then the algorithm doesn’t need to select a new set, and otherwise the algorithm has to select a set into A that contains et . The goal of the algorithm is to minimize the size of A. Show that there are problem instances such that the offline optimal solution has |A| = O(1) but any deterministic online algorithm has size Ω(log m). Hint: You may prove the lower bound even against an online algorithm that is allowed to maintain a fractional set cover, i.e., it maintains ~x ∈ [0, 1]m such that P i : et∈Si xi ≥ 1 and the algorithm is only allowed to increase the coordinates of ~x.
Extra Credit:
§1 (Extra credit) Calculate the eigenvectors and eigenvalues of the (adjacency matrix of the) n-dimensional boolean hypercube, which is the graph with vertex set {−1, 1} n and x, y are connected by an edge iff they differ in exactly one of the n locations. (Hint: Use symmetry extensively.)
§2 (Open Problem) Can you extend the discrepancy result in Problem 5 to every prefix, i.e., find a coloring ~ε such that maxt k P i≤t ~aiεik∞ = O(s)? Can you prove this result for some other function f(s) that does not depend on n and T (like f(s) = 2s )?