高级算法 (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

In this problem, we investigate some properties about the detail balanced equation.

• Let [math]\displaystyle{ \Omega }[/math] be a finite set, [math]\displaystyle{ \pi: \Omega \to \mathbb{R} }[/math] be a distribution over [math]\displaystyle{ \Omega }[/math], and [math]\displaystyle{ P \in \mathbb{R}^{\Omega\times\Omega} }[/math] be a Markov chain. Suppose for all [math]\displaystyle{ x, y \in \Omega }[/math], it holds that [math]\displaystyle{ \pi(x) P(x, y) = \pi(y) P(y, x) }[/math]. Now, let [math]\displaystyle{ t \gt 0 }[/math] be an integer, show that for all [math]\displaystyle{ x, y \in \Omega }[/math], it also holds that [math]\displaystyle{ \pi(x) P^t(x, y) = \pi(y) P^t(y, x) }[/math].
• Let [math]\displaystyle{ \Omega }[/math] be a finite set, [math]\displaystyle{ \pi: \Omega \to \mathbb{R} }[/math] be a distribution over [math]\displaystyle{ \Omega }[/math], and [math]\displaystyle{ P \in \mathbb{R}^{\Omega\times\Omega} }[/math] be a Markov chain. For all [math]\displaystyle{ f, g \in \mathbb{R}^\Omega }[/math], an inner product [math]\displaystyle{ \langle \cdot, \cdot\rangle_\pi }[/math] with respect to [math]\displaystyle{ \pi }[/math] is defined as [math]\displaystyle{ \langle f, g \rangle_\pi \triangleq \sum_{x \in \Omega} \pi(x) f(x) g(x) }[/math].We want you to prove an equivalent variant for the detail balanced equation:

[math]\displaystyle{ \begin{align} \forall x, y \in \Omega, \quad \pi(x)P(x, y) = \pi(y)P(y, x) \quad \Leftrightarrow \quad \forall f, g \in \mathbb{R}^\Omega, \quad \langle f, P g \rangle_\pi = \langle P f, g \rangle_\pi. \end{align} }[/math]

• Let [math]\displaystyle{ \Omega_1, \Omega_2 }[/math] be two finite sets. Let [math]\displaystyle{ \pi_1, \pi_2 }[/math] be two distributions on [math]\displaystyle{ \Omega_1 }[/math] and [math]\displaystyle{ \Omega_2 }[/math], respectively. Let [math]\displaystyle{ P_{12} \in \mathbb{R}^{\Omega_1 \times \Omega_2} }[/math] and [math]\displaystyle{ P_{21} \in \mathbb{R}^{\Omega_2 \times \Omega_1} }[/math] be two Markov chains. Show that:

[math]\displaystyle{ \begin{align} \forall x \in \Omega_1, y \in \Omega_2, \quad \pi_1(x)P_{12}(x, y) = \pi_2(y)P_{21}(y, x) \quad \Leftrightarrow \quad \forall f \in \mathbb{R}^{\Omega_1}, g: \mathbb{R}^{\Omega_2}, \quad \langle f, P_{12} g \rangle_{\pi_1} = \langle P_{21} f, g \rangle_{\pi_2}. \end{align} }[/math]

[math]\displaystyle{ \quad }[/math] Moreover, assuming that [math]\displaystyle{ P_{12}, P_{21} }[/math] satisfy [math]\displaystyle{ \forall x \in \Omega_1, y \in \Omega_2, \pi_1(x)P_{12}(x, y) }[/math], show that [math]\displaystyle{ P = P_{12}P_{21} }[/math] is positive semidefinite w.r.t. [math]\displaystyle{ \langle \cdot, \cdot\rangle_{\pi_1} }[/math] (i.e. [math]\displaystyle{ \forall f, \langle f, P f\rangle_{\pi_1} \geq 0 }[/math]).