Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due
COS 521:Advanced Algorithms Homework 2
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
Suppose that you are allowed only a single pass over a large document of English words. Your goal is to (approximately) calculate the number of words n in this document using very little space. The naive algorithm which maintains a counter of the number of seen words uses O(log n) space (bits).
(a) Consider an algorithm that maintains a counter X, initialized to 0, and on seeing the next word increases X by 1 with probability 1 2X (otherwise, does nothing and move to the next word). Show that at the end of the stream, E[2X] = n + 1 and E[22X] = 3 2 n 2 + 3 2 n + 1. (Hint: You may want to use induction.)
(b) Assuming Part (a), show for 0 < < 1/2 how we can use O( 1 2 · loglog n) space to output with probability at least 0.9 a number ˆn ∈ [ n 1+ , n(1 + )].
§2 Recall the max-flow problem from undergraduate algorithms: for a directed graph G(V, E) with non-negative capacities ce for every e ∈ E and two special vertices s (source, with no incoming edges) and t (sink, with no outgoing edges), a flow in G is an assignment f : E → R≥0 such that f(e) ≤ ce for every edge and for every vertex v ∈ V \ {s, t}, the total incoming flow P (u,v)∈E f((u, v)) equals the total outgoing flow P (v,w)∈E P f((v, w)). The task is to find a maximum flow f i.e., a flow f such that (s,u)∈E f((s, u)) is maximized.
(a) Show that the following LP is a valid formulation for computing the value of the maximum flow in G. There is a variable f((u, v)) for all (u, v) ∈ E. (Hint: below, the inequality between the flows is not a typo. You should show that it is w.l.o.g. to replace the equality with inequality, as this will make it easier to reason about later parts.)
maxX u f((u, t))
∀e = (u, v) ∈ E, f((u, v)) ≤ ce
∀v /∈ {s, t}, X (u,v)∈E f((u, v)) ≥ X (v,w)∈E f((v, w))
∀e ∈ E, f(e) ≥ 0 (1)
(b) Write the dual for the LP (1). Show that this dual LP computes the minimum fractional s-t cut in G (a cut that separates s and t in G and minimizes the sum of the capacities ce of the edges going across it. You will know what a fractional s-t cut is once you take the dual: every node isn’t entirely on the s side or the t side, but rather partially on each). Use strong LP duality to conclude the fractional max-flow min-cut theorem. That is, if the max-flow is C, there exists a fractional s-t cut of value C, and no fractional s-t cut of value < C.
(c) Devise a rounding scheme that takes as input a fractional min-cut of value C and outputs a true (deterministic) min-cut of value C. (Hint: there is a simple rounding scheme that works, but it is not a rounding scheme we have already seen in class.)
§3 (Firehouse location) Suppose we model a city as an m-point finite metric space with d(x, y) denoting the distance between points x, y. These m 2 distances (which satisfy triangle inequality) are given as part of the input. The city has n houses located at points v1, v2, . . . , vn in this metric space. The city wishes to build k firehouses and asks you to help find the best locations c1, c2, . . . , ck for them, which can be located at any of the m points in the city. The happiness of a town resident with the final locations depends upon his distance from the closest firehouse. So you decide to minimize the cost function Pn i=1 d(vi , ui) where ui ∈ {c1, c2, . . . , ck} is the firehouse closest to vi . Describe an LP-rounding-based algorithm that runs in poly(m) time and solves this problem approximately. If OPT is the optimum cost of a solution with k firehouses, your solution is allowed to use O(k log n) firehouses and have cost at most OPT.1 Specifically, you should design an algorithm which runs in polynomial time, and uses O(k log n) firehouses in expectation, and also has cost at most OPT in expectation.
§4 (Approximate LP Solving via Multiplicative Weights) This exercise develops an algorithm to approximately solve Linear Programs.
Consider the problem of finding if a system of linear inequalities as below admits a solution - i.e., whether the system is feasible. This is an example of a feasibility linear program and while it appears restrictive, one can use it solve arbitrary linear programs to obtain approximate solutions. For all subparts, you may assume that |aij | ≤ 1 and |bi | ≤ 1 for all i, j.
a > 1 x ≥ b1 a > 2 x ≥ b2 . . . a > mx ≥ bm xi ≥ 0 ∀ i ∈ [n] Xn i=1 xi = 1. (2)
(a) Design a simple algorithm to solve the following linear program, which has only two non-trivial constraints. Below, the weights w1, w2, . . . , wm are fixed (along with the vectors a > j and numbers bj ), and x1, . . . , xn are the variables. maxXm j=1 wj (a > j x − bj ) xi ≥ 0 ∀i ∈ [n] Xn i=1 xi = 1. (3)
(b) Prove that if there exist non-negative weights w1, w2, . . . , wm such that the value of the program above is negative, then the system (2) is infeasible.
(c) The above setting of finding weights that certify infeasibility of (2) might remind you of the setting of weighting the experts via multiplicative weights update rule discussed in the class. Use these ideas to obtain an algorithm that a) either finds a set of non-negative weights certifying infeasibility of LP in (2) or b) finds a solution x that approximately satisfies all the constraints in (2), i.e., for each 1 ≤ j ≤ m, a > j x − bj ≥ −, and for each 1 ≤ i ≤ n, xi ≥ 0, and Pn i=1 xi = 1. Prove that your algorithm terminates after solving O(ln(m)/ε2 ) LPs of form (3) (you do not need to analyze the remaining runtime). (Hint: Identify m “experts” - one for each inequality constraint in (2) and maintain a weighting of experts (starting with the uniform weighting of all 1s, say) for times t = 0, 1, . . . , - these are your progressively improving guesses for the weights. Solve (3) using the weights at time t. If the value of (3) is negative, you are done, otherwise think of the “cost” of the j th expert as a > j x (t) −bj where x (t) is the solution to the LP (3) at time t and update the weights.)
§5 (extra credit) In a combinatorial auction there are n bidders and m items. Bidder i has a monotone valuation function vi(·) where vi(S) denotes their value for set S of items (and vi(S ∪T) ≥ vi(S) for all S, T). A Walrasian Equilibrium is a price for each item ~p such that:
• Each buyer i selects to purchase a set Bi ∈ arg maxS{vi(S) − P j∈S pj}.
• The sets Bi are disjoint, and ∪iBi = [m].
Prove that a Walrasian equilibrium exists for v1, . . . , vn if and only if the optimum of the LP relaxation below (called the configuration LP) is achieved at an integral point (i.e. where each xi,S ∈ {0, 1}). Hint: use strong duality!
maxX i X S vi(S) · xi,S ∀i, X S xi,S = 1 ∀j, X S3j X i xi,S ≤ 1
Also, come up with an example of two valuation functions v1, v2 over two items where a Walrasian equilibrium doesn’t exist.