高级算法 (Fall 2021)/Problem Set 4

• 每道题目的解答都要有完整的解题过程。中英文不限。

Problem 1

Given a graph [math]\displaystyle{ G = (V, E) }[/math], and weights [math]\displaystyle{ \{w_e\}_{e\in E} }[/math] for each edge, the maximum weight matching problem is the problem of finding a matching in which the sum of weights is maximized. The following ILP is built for the maximum weight matching problem.

[math]\displaystyle{ \begin{align} \textrm{maximize} & \sum_{e \in E} w_e x_e \\ \textrm{s.t.} & \sum_{e \ni v} x_e \leq 1, \forall v \in V \\ & x_e \in \{0, 1\}, \forall e \in E. \end{align} }[/math]

• Give the dual-relaxed program of the above ILP.
• Relax complementary slackness conditions appropriately, and show that the integrality gap of this ILP is at least 1/2.

Problem 2

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 [math]\displaystyle{ 2 }[/math] (so a [math]\displaystyle{ 2 }[/math]-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 [math]\displaystyle{ 2 }[/math]-colored so that no edge is monochromatic. What's the smallest value of [math]\displaystyle{ k }[/math] you can achieve?

Problem 3

Suppose we have graphs [math]\displaystyle{ G=(V,E) }[/math] and [math]\displaystyle{ H=(V,F) }[/math] on the same vertex set. We wish to partition [math]\displaystyle{ V }[/math] into clusters [math]\displaystyle{ V_1,V_2,\cdots }[/math] so as to maximize:

[math]\displaystyle{ (\#\text{ of edges in }E\text{ that lie within clusters})+(\#\text{ of edges in }F\text{ that lie between clusters}). }[/math]

• Show that the following SDP is an upperbound on this.

[math]\displaystyle{ \text{maximize}\qquad\sum_{(u,v)\in E}\langle x_u,x_v\rangle+\sum_{(u,v)\in F}(1-\langle x_u,x_v\rangle) \\ \begin{align} \text{subject to} && \langle x_u,x_u\rangle & =1, & \forall u & \in V, \\ && \langle x_u,x_v\rangle & \ge0, & \forall u,v & \in V, \\ && x_u & \in\mathbb R^{|V|}, & \forall u & \in V. \end{align} }[/math]

• Describe a clustering into [math]\displaystyle{ 4 }[/math] clusters that achieves an objective value [math]\displaystyle{ 0.75 }[/math] times the SDP value. (Hint: Use Goemans-Williamson style rounding but with two random hyperplanes instead of one. You may need a quick matlab calculation just like GW.)

Problem 4

(MCMC)