高级算法 (Fall 2018)/Problem Set 5

每道题目的解答都要有完整的解题过程、分析和证明。中英文不限。

Problem 1

In the facility location problem, some clients may be far away from all facilities. If we require every client to be connected to at least one open facility, a big portion of the total cost is due to connecting these remote clients. This observation motivates the following variant of the facility location problem: for each client [math]\displaystyle{ j\in C }[/math] we associate a penalty [math]\displaystyle{ p_j\gt 0 }[/math], and we must pay [math]\displaystyle{ p_j }[/math] if client [math]\displaystyle{ j }[/math] is not connected to any open facility. The objective is to minimize the sum of the connection costs, facility open costs, and penalties.

(a) Give the primal integer linear program for this variant of the facility location problem, its LP-relaxation and the dual LP.

(b) Modify the 3-approximation algorithm for the facility location problem to obtain an algorithm for this variant. Describe your modified algorithm.

(c) Prove your modified algorithm is a 3-approximation algorithm for this variant.

Problem 2

Assume we have a set [math]\displaystyle{ V }[/math] containing [math]\displaystyle{ n }[/math] different images. We are also given two multisets [math]\displaystyle{ E^+ }[/math] and [math]\displaystyle{ E^- }[/math], each of which is a multiset of pairs of images. Each element [math]\displaystyle{ (i,j) }[/math] in [math]\displaystyle{ E^+ }[/math] means some user has marked image [math]\displaystyle{ i }[/math] and image [math]\displaystyle{ j }[/math] as similar, while each element [math]\displaystyle{ (i,j) }[/math] in [math]\displaystyle{ E^- }[/math] means some user has marked image [math]\displaystyle{ i }[/math] and image [math]\displaystyle{ j }[/math] as dissimilar. Notice, these ratings were generated by different users and may be inconsistent. That is, some image pair [math]\displaystyle{ (i,j) }[/math] may appear in both [math]\displaystyle{ E^+ }[/math] and [math]\displaystyle{ E^- }[/math]. Call elements in [math]\displaystyle{ E^+ }[/math] as [math]\displaystyle{ + }[/math]edges, and elements in [math]\displaystyle{ E^- }[/math] as [math]\displaystyle{ - }[/math]edges. We wish to partition images into clusters [math]\displaystyle{ S_1,S_2,\cdots }[/math] so as to maximize: (number of [math]\displaystyle{ + }[/math]edges that lie within clusters) [math]\displaystyle{ + }[/math] (number of [math]\displaystyle{ - }[/math]edges that lie between clusters).

(a) Argue that the following SDP gives an upper bound of the above objective, where [math]\displaystyle{ w^+_{(i,j)} }[/math] and [math]\displaystyle{ w^-_{(i,j)} }[/math] denote the number of times image pair [math]\displaystyle{ (i,j) }[/math] has appeared in [math]\displaystyle{ E^+ }[/math] and [math]\displaystyle{ E^- }[/math], respectively.

[math]\displaystyle{ \begin{align} \text{maximize}\quad & \sum_{i\in V, j\in V, i\lt j}w^+_{(i,j)}\cdot\langle \mathbf{x}_i,\mathbf{x}_j\rangle+w^-_{(i,j)}\cdot\left(1-\langle \mathbf{x}_i,\mathbf{x}_j\rangle\right)\\ \text{subject to} \quad& \lVert \mathbf{x}_i\rVert^2_2= 1,\qquad \forall i\in V,\\ & \langle \mathbf{x}_i,\mathbf{x}_j\rangle \ge 0,\qquad \forall i\in V,j\in V, i\ne j\\ & \mathbf{x}_i\in\mathbb{R}^n, \qquad \forall i\in V. \end{align} }[/math]

(b) Devise a randomized algorithm that partition images into 4 clusters and in expectation achieves an objective value 0.75 times the optimal SDP value. Hint: use Goemans-Williamson style rounding but with two random hyperplanes instead of one.

Problem 3

A [math]\displaystyle{ k }[/math]-uniform hypergraph is an ordered pair [math]\displaystyle{ G=(V,E) }[/math], where [math]\displaystyle{ V }[/math] denotes the set of vertices and [math]\displaystyle{ E }[/math] denotes the set of edges. Moreover, each edge in [math]\displaystyle{ E }[/math] now contains [math]\displaystyle{ k }[/math] distinct vertices, instead of 2. (So a 2-uniform hypergraph is just what we normally call a graph.) A hypergraph is [math]\displaystyle{ k }[/math]-regular if all vertices have degree [math]\displaystyle{ k }[/math]; that is, each vertex is exactly contained within [math]\displaystyle{ k }[/math] hypergraph edges.

Show that for sufficiently large [math]\displaystyle{ k }[/math], the vertices of a [math]\displaystyle{ k }[/math]-uniform, [math]\displaystyle{ k }[/math]-regular hypergraph can be 2-colored so that no edge is monochromatic. What’s the smallest value of [math]\displaystyle{ k }[/math] you can achieve?

Programming Assignment

Finally, you can get your hands dirty and do some coding! You do not need to hand in solutions or source-code or anything for this programming assignment, but you should find some time to actually do this, so as to better understand the algorithmic Lovász Local Lemma.

More specifically, you will implement Moser's algorithm introduced in class for the following scenario. Consider a 9-SAT formula where each variable appears in 8 clauses. Set up a formula with 112,500 variables and 100,000 clauses in the following manner: set up 8 copies of each of the 112,500 variables (900,000 total variables), permute them, and use the ordering to assign the variables to the 100,000 clauses. (If a variable appears in a clause multiple times, try to locally correct this by swapping one copy to another clause.) Then assign a random "sign" to each variable: with probability 1/2, use [math]\displaystyle{ \overline{x} }[/math] instead of [math]\displaystyle{ x }[/math]. This gives a formula that satisfies the condition [math]\displaystyle{ d\leq 2^{k-3}-1 }[/math]. (Try verify this!)

For each execution of your implementation, you should track how many times the local correction procedure (i.e., [math]\displaystyle{ \texttt{Fix} }[/math]) is required before termination. Repeat this experiment with 100 (or more) different formulas derived from the process above, and observe the distribution of the number of local corrections required. Note that you may want to take some care to make the local correction step efficient in order to have your program run effectively.