高级算法 (Fall 2021)/Problem Set 3 and 高级算法 (Fall 2021)/Problem Set 4: Difference between pages

From TCS Wiki
(Difference between pages)
Jump to navigation Jump to search
VisualWikitext
imported>TCSseminar
No edit summary
 
imported>TCSseminar
 
Line 2: Line 2:


== Problem 1 ==
== Problem 1 ==
In this problem, we will demonstrate a common algorithmic application of the Johnson-Lindenstrauss Theorem (JLT). Specifically, we will consider the ''<math>k</math>-means clustering'' problem, which is widely used in areas like machine learning and data mining.


In the <math>k</math>-means clustering problem, we are given <math>n</math> points <math>\mathbf{x}_1,\cdots,\mathbf x_n\in\mathbb{R}^d</math>, and the goal is to partition these points into <math>k</math> disjoint sets (or, cluster) <math>C_1,\cdots,C_k</math> so as to minimize the cost:
== 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).
:<math>\texttt{cost}(\mathbf{x}_1,\cdots,\mathbf{x}_n,C_1,\cdots,C_k)=\sum_{i=1}^{k}\sum_{j\in C_i}\lVert\mathbf{x}_j-\mathbf{\mu}_i\rVert^2_2</math>
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.
 
Here, <math>\mathbf{\mu}_i=(1/|C_i|)\cdot\sum_{j\in C_i}\mathbf{x}_j</math> is the mean of the points in cluster <math>C_i</math>. In other words, we want to find <math>k</math> clusters that have as little internal variance as possible.
 
'''(a)''' Prove the following equality:
 
:<math>\texttt{cost}(\mathbf{x}_1,\cdots,\mathbf{x}_n,C_1,\cdots,C_k)=\sum_{i=1}^{k}\frac{1}{|C_i|}\sum_{j,l\in C_i,j<l}\lVert\mathbf{x}_j-\mathbf{x}_l\rVert^2_2</math>
 
'''(b)''' Suppose we use the Johnson-Lindenstrauss method taught in class to embed <math>\mathbf{x}_1,\cdots,\mathbf{x}_n</math> into <math>O(\log{n}/\epsilon^2)</math>-dimensional points <math>\mathbf{\tilde{x}}_1,\cdots,\mathbf{\tilde{x}}_n</math>. Show that with high probability in <math>n</math>, the following inequality holds for all clusters:
:<math>
(1-\epsilon)\texttt{cost}(\mathbf{x}_1,\cdots,\mathbf{x}_n,C_1,\cdots,C_k)
\leq\texttt{cost}(\mathbf{\tilde{x}}_1,\cdots,\mathbf{\tilde{x}}_n,C_1,\cdots,C_k)
\leq(1+\epsilon)\texttt{cost}(\mathbf{x}_1,\cdots,\mathbf{x}_n,C_1,\cdots,C_k)
</math>


'''(c)''' Suppose we know a set of clusters (i.e., a partition of the <math>n</math> points) <math>\tilde{C}_1,\cdots,\tilde{C}_k</math> such that:
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?


:<math>\texttt{cost}(\mathbf{\tilde{x}}_1,\cdots,\mathbf{\tilde{x}}_n,\tilde{C}_1,\cdots,\tilde{C}_k)\leq\gamma\cdot\texttt{cost}(\mathbf{\tilde{x}}_1,\cdots,\mathbf{\tilde{x}}_n,\tilde{C}^*_1,\cdots,\tilde{C}^*_k)</math>
== 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 maximise:
:<math>(\#\text{ of edges in }E\text{ that lie within clusters})+(\#\text{ of edges in }F\text{ that lie between clusters}).</math>


where <math>\tilde{C}^*_1,\cdots,\tilde{C}^*_k</math> is the optimal partition for points <math>\mathbf{\tilde{x}}_1,\cdots,\mathbf{\tilde{x}}_n</math>. That is, assume we know a <math>\gamma</math> approximation to the optimal clustering for the dimensionality reduced points. Show that, when <math>\epsilon\leq 1/2</math>,
* Show that the following SDP is an upperbound on this.
 
:<math>\texttt{cost}(\mathbf{x}_1,\cdots,\mathbf{x}_n,\tilde{C}_1,\cdots,\tilde{C}_k)\leq(1+O(\epsilon))\cdot\gamma\cdot\texttt{cost}(\mathbf{x}_1,\cdots,\mathbf{x}_n,C^*_1,\cdots,C^*_k)</math>
 
where <math>C^*_1,\cdots,C^*_k</math> is the optimal partition for <math>\mathbf{x}_1,\cdots,\mathbf{x}_n</math>.
 
In other words, we can compute an approximately optimal clustering for high dimensional original data using just the dimensionality reduced data. In many cases, this approach will speed up algorithms for solving <math>k</math>-means clustering.
 
== Problem 2 ==
The following is the weighted version of set cover problem:
 
Given <math>m</math> subsets <math>S_1,S_2,\ldots,S_m\subseteq U</math>, where <math>U</math> is a universe of size <math>n=|U|</math>, and each subset <math>S_i</math> is assigned a positive weight <math>w_i>0</math>, the goal is to find a <math>C\subseteq\{1,2,\ldots,m\}</math> such that <math>U=\bigcup_{i\in C}S_i</math> and the total weight <math>\sum_{I\in C}w_i</math> is minimized.
* Give an integer program for the problem and its LP relaxation.
* Consider the following idea of randomized rounding: independently round each fractional value to <math>\{0,1\}</math> with the probability of the fractional value itself; and repeatedly apply this process to the variables rounded to 0 in previous iterations until <math>U</math> is fully covered. Show that this can return a set cover with <math>O(\log n)</math> approximation ratio with probability at least <math>0.99</math>.
 
== Problem 3==
In the ''maximum directed cut'' (MAX-DICUT) problem, we are given as input a directed graph <math>G(V,E)</math>. The goal is to partition <math>V</math> into disjoint <math>S</math> and <math>T</math> so that the number of edges in <math>E(S,T)=\{(u,v)\in E\mid u\in S, v\in T\}</math> is maximized. The following is the integer program for MAX-DICUT:
:::<math>
:::<math>
\text{maximize} &&& \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}
\begin{align}
\text{maximize} &&& \sum_{(u,v)\in E}y_{u,v}\\
\text{subject to} && \langle x_u,x_u\rangle & =1, & \forall u & \in V, \\
\text{subject to} && y_{u,v} &\le x_u, & \forall (u,v)&\in E,\\
&& \langle x_u,x_v\rangle & \ge0, & \forall u,v & \in V, \\
&& y_{u,v} &\le 1-x_v, & \forall (u,v)&\in E,\\
&& x_u & \in R^n, & \forall u & \in V.
&& x_v &\in\{0,1\}, & \forall v&\in V,\\
&& y_{u,v} &\in\{0,1\}, & \forall (u,v)&\in E.
\end{align}
\end{align}
</math>
</math>
Let <math>x_v^*,y_{u,v}^*</math> denote the optimal solution to the '''LP-relaxation''' of the above integer program.
* Apply the randomized rounding such that for every <math>v\in V</math>, <math>\hat{x}_v=1</math> independently with probability <math>x_v^*</math>. Analyze the approximation ratio (between the expected size of the random cut and OPT).
* Apply another randomized rounding such that for every <math>v\in V</math>, <math>\hat{x}_v=1</math> independently with probability <math>1/4+x_v^*/2</math>. Analyze the approximation ratio for this algorithm.
== Problem 4 ==

Revision as of 08:10, 20 December 2021

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

Problem 1

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 maximise:

[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} &&& \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 R^n, & \forall u & \in V. \end{align} }[/math]
Retrieved from "https://tcs.nju.edu.cn/wiki/index.php?title=高级算法_(Fall_2021)/Problem_Set_3&oldid=9698"