高级算法 (Fall 2021)/Problem Set 4: Difference between revisions

From TCS Wiki
Jump to navigation Jump to search
imported>TCSseminar
imported>TCSseminar
 
(49 intermediate revisions by the same user not shown)
Line 2: Line 2:


== Problem 1 ==
== 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 ==
== Problem 2 ==
Line 12: Line 23:
== Problem 3 ==
== Problem 3 ==
Suppose we have graphs <math>G=(V,E)</math> and <math>H=(V,F)</math> on the same vertex set.
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 maximise:
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 detailed balance equation.
* Let <math>\Omega</math> be a finite set, <math>\pi: \Omega \to \mathbb{R}_{>0}</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}_{>0}</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 an equivalent variant for the detailed balance 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:\Omega_1 \to \mathbb{R}_{>0}, \pi_2 :\Omega_2 \to \mathbb{R}_{>0} </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 \in \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 that <math>P_{12}, P_{21}</math> satisfy <math>\forall x \in \Omega_1, y \in \Omega_2, \pi_1(x)P_{12}(x, y) = \pi_2(y)P_{21}(y, x)</math>, show that <math>P = P_{12}P_{21}</math> is positive semidefinite.

Latest revision as of 04:54, 26 December 2021

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

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 detailed balance equation.

  • Let [math]\displaystyle{ \Omega }[/math] be a finite set, [math]\displaystyle{ \pi: \Omega \to \mathbb{R}_{\gt 0} }[/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}_{\gt 0} }[/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 detailed balance 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:\Omega_1 \to \mathbb{R}_{\gt 0}, \pi_2 :\Omega_2 \to \mathbb{R}_{\gt 0} }[/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 \in \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) = \pi_2(y)P_{21}(y, x) }[/math], show that [math]\displaystyle{ P = P_{12}P_{21} }[/math] is positive semidefinite.