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

*每道题目的解答都要有<font color="red" size=5>完整的解题过程</font>。中英文不限。

== Problem 1 ==
Given a graph <math>G = (V, E)</math>, and weights <math>\{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>
\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>k</math>-uniform hypergraph'' is an ordered pair <math>G=(V,E)</math>, where <math>V</math> denotes the set of vertices and <math>E</math> denotes the set of edges. Moreover, each edge in <math>E</math> now contains <math>k</math> distinct vertices, instead of <math>2</math> (so a <math>2</math>-uniform hypergraph is just what we normally call a graph).
A hypergraph is <math>k</math>-regular if all vertices have degree <math>k</math>; that is, each vertex is exactly contained within <math>k</math> hypergraph edges.

Show that for sufficiently large <math>k</math>, the vertices of a <math>k</math>-uniform, <math>k</math>-regular hypergraph can be <math>2</math>-colored so that no edge is monochromatic.
What's the smallest value of <math>k</math> you can achieve?

== Problem 3 ==
Suppose we have graphs <math>G=(V,E)</math> and <math>H=(V,F)</math> on the same vertex set.
We wish to partition <math>V</math> into clusters <math>V_1,V_2,\cdots</math> so as to maximize:
:<math>(\#\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>
\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>4</math> clusters that achieves an objective value <math>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>\Omega</math> be a finite set, <math>\pi: \Omega \to \mathbb{R}</math> be a distribution over <math>\Omega</math>, and <math>P \in \mathbb{R}^{\Omega\times\Omega}</math> be a Markov chain. Suppose for all <math> x, y \in \Omega </math>, it holds that <math> \pi(x) P(x, y) = \pi(y) P(y, x) </math>. Now, let <math> t > 0 </math> be an integer, show that for all <math> x, y \in \Omega </math>, it also holds that <math> \pi(x) P^t(x, y) = \pi(y) P^t(y, x) </math>.
* Let <math>\Omega</math> be a finite set, <math>\pi: \Omega \to \mathbb{R}</math> be a distribution over <math>\Omega</math>, and <math>P \in \mathbb{R}^{\Omega\times\Omega}</math> be a Markov chain. For all <math>f, g \in \mathbb{R}^\Omega</math>, an inner product <math>\langle \cdot, \cdot\rangle_\pi</math> with respect to <math>\pi</math> is defined as <math>\langle f, g \rangle_\pi \triangleq \sum_{x \in \Omega} \pi(x) f(x) g(x)</math>.We want you to prove a equivalent variant for the detail balanced equation:
:<math>
\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>\Omega_1, \Omega_2</math> be two finite sets. Let <math>\pi_1, \pi_2</math> be two distributions on <math>\Omega_1</math> and <math>\Omega_2</math>, respectively. Let <math> P_{12} \in \mathbb{R}^{\Omega_1 \times \Omega_2} </math> and <math> P_{21} \in \mathbb{R}^{\Omega_2 \times \Omega_1} </math> be two Markov chains. Show that:
:<math>
\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>\quad</math> Moreover, assuming <math>P_{12}, P_{21}</math> satisfy <math>\forall x \in \Omega_1, y \in \Omega_2, \pi_1(x)P_{12}(x, y)</math>, show that <math>P = P_{12}P_{21}</math> is positive semidefinite w.r.t. <math>\langle \cdot, \cdot\rangle_{\pi_1} </math> (i.e. <math>\forall f, \langle f, P f\rangle_{\pi_1} \geq 0</math>).