计算复杂性 (Fall 2018)/作业5已提交名单 and 高级算法 (Fall 2018)/Problem Set 4: Difference between pages
imported>TCSseminar No edit summary |
imported>TCSseminar (Created page with "''Note: in this problem set, only problem 1 and 2 are mandatory. For problem 3 to 5, you are only required to solve arbitrary two of them. (But you are also welcome to hand in...") |
||
Line 1: | Line 1: | ||
''Note: in this problem set, only problem 1 and 2 are mandatory. For problem 3 to 5, you are only required to solve arbitrary two of them. (But you are also welcome to hand in solutions for them all!)'' | |||
{ | == Problem 1== | ||
Let <math>G(V,E)</math> be an undirected graph with positive edge weights <math>w:E\to\mathbb{Z}^+</math>. Given a partition of <math>V</math> into <math>k</math> disjoint subsets <math>S_1,S_2,\ldots,S_k</math>, we define | |||
:<math>w(S_1,S_2,\ldots,S_k)=\sum_{uv\in E\atop \exists i\neq j: u\in S_i,v\in S_j}w(uv)</math> | |||
as the cost of the '''<math>k</math>-cut''' <math>\{S_1,S_2,\ldots,S_k\}</math>. Our goal is to find a <math>k</math>-cut with maximum cost. | |||
# Give a poly-time greedy algorithm for finding the weighted max <math>k</math>-cut. Prove that the approximation ratio is <math>(1-1/k)</math>. | |||
| | # Consider the following local search algorithm for the weighted max cut (max 2-cut). | ||
::Fill in the blank parenthesis. Give an analysis of the running time of the algorithm. And prove that the approximation ratio is 0.5. | |||
start with an arbitrary bipartition of <math>V</math> into disjoint <math>S_0,S_1</math>; | |||
while (true) do | |||
if <math>\exists i\in\{0,1\}</math> and <math>v\in S_i</math> such that <font color=red>(______________)</font> | |||
then <math>v</math> leaves <math>S_i</math> and joins <math>S_{1-i}</math>; | |||
continue; | |||
end if | |||
break; | |||
end | |||
== Problem 2== | |||
Given <math>m</math> subsets <math>S_1,S_2,\ldots, S_m\subseteq U</math> of a universe <math>U</math> of size <math>n</math>, we want to find a <math>C\subseteq\{1,2,\ldots, {m}\}</math> of fixed size <math>k=|C|</math> with the maximum '''coverage''' <math>\left|\bigcup_{i\in C}S_i\right|</math>. | |||
* Give a poly-time greedy algorithm for the problem. Prove that the approximation ratio is <math>1-(1-1/k)^k>1-1/e</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> | |||
\begin{align} | |||
\text{maximize} &&& \sum_{(u,v)\in E}y_{u,v}\\ | |||
\text{subject to} && y_{u,v} &\le x_u, & \forall (u,v)&\in E,\\ | |||
&& y_{u,v} &\le 1-x_v, & \forall (u,v)&\in E,\\ | |||
&& x_v &\in\{0,1\}, & \forall v&\in V,\\ | |||
&& y_{u,v} &\in\{0,1\}, & \forall (u,v)&\in E. | |||
\end{align} | |||
</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== | |||
Recall the MAX-SAT problem and its integer program: | |||
:::<math> | |||
\begin{align} | |||
\text{maximize} &&& \sum_{j=1}^my_j\\ | |||
\text{subject to} &&& \sum_{i\in S_j^+}x_i+\sum_{i\in S_j^-}(1-x_i)\ge y_j, && 1\le j\le m,\\ | |||
&&& x_i\in\{0,1\}, && 1\le i\le n,\\ | |||
&&& y_j\in\{0,1\}, && 1\le j\le m. | |||
\end{align} | |||
</math> | |||
Recall that <math>S_j^+,S_j^-\subseteq\{1,2,\ldots,n\}</math> are the respective sets of variables appearing positively and negatively in clause <math>j</math>. | |||
Let <math>x_i^*,y_j^*</math> denote the optimal solution to the '''LP-relaxation''' of the above integer program. In our class we learnt that if <math>\hat{x}_i</math> is round to 1 independently with probability <math>x_i^*</math>, we have approximation ratio <math>1-1/\mathrm{e}</math>. | |||
We consider a generalized rounding scheme such that every <math>\hat{x}_i</math> is round to 1 independently with probability <math>f(x_i^*)</math> for some function <math>f:[0,1]\to[0,1]</math> to be specified. | |||
* Suppose <math>f(x)</math> is an arbitrary function satisfying that <math>1-4^{-x}\le f(x)\le 4^{x-1}</math> for any <math>x\in[0,1]</math>. Show that with this rounding scheme, the approximation ratio (between the expected number of satisfied clauses and OPT) is at least <math>3/4</math>. | |||
* Derandomize this algorithm through conditional expectation and give a deterministic polynomial time algorithm with approximation ratio <math>3/4</math>. | |||
* Is it possible that for some more clever <math>f</math> we can do better than this? Try to justify your argument. | |||
==Problem 5 == | |||
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>. |
Revision as of 12:56, 12 November 2018
Note: in this problem set, only problem 1 and 2 are mandatory. For problem 3 to 5, you are only required to solve arbitrary two of them. (But you are also welcome to hand in solutions for them all!)
Problem 1
Let [math]\displaystyle{ G(V,E) }[/math] be an undirected graph with positive edge weights [math]\displaystyle{ w:E\to\mathbb{Z}^+ }[/math]. Given a partition of [math]\displaystyle{ V }[/math] into [math]\displaystyle{ k }[/math] disjoint subsets [math]\displaystyle{ S_1,S_2,\ldots,S_k }[/math], we define
- [math]\displaystyle{ w(S_1,S_2,\ldots,S_k)=\sum_{uv\in E\atop \exists i\neq j: u\in S_i,v\in S_j}w(uv) }[/math]
as the cost of the [math]\displaystyle{ k }[/math]-cut [math]\displaystyle{ \{S_1,S_2,\ldots,S_k\} }[/math]. Our goal is to find a [math]\displaystyle{ k }[/math]-cut with maximum cost.
- Give a poly-time greedy algorithm for finding the weighted max [math]\displaystyle{ k }[/math]-cut. Prove that the approximation ratio is [math]\displaystyle{ (1-1/k) }[/math].
- Consider the following local search algorithm for the weighted max cut (max 2-cut).
- Fill in the blank parenthesis. Give an analysis of the running time of the algorithm. And prove that the approximation ratio is 0.5.
start with an arbitrary bipartition of [math]\displaystyle{ V }[/math] into disjoint [math]\displaystyle{ S_0,S_1 }[/math]; while (true) do if [math]\displaystyle{ \exists i\in\{0,1\} }[/math] and [math]\displaystyle{ v\in S_i }[/math] such that (______________) then [math]\displaystyle{ v }[/math] leaves [math]\displaystyle{ S_i }[/math] and joins [math]\displaystyle{ S_{1-i} }[/math]; continue; end if break; end
Problem 2
Given [math]\displaystyle{ m }[/math] subsets [math]\displaystyle{ S_1,S_2,\ldots, S_m\subseteq U }[/math] of a universe [math]\displaystyle{ U }[/math] of size [math]\displaystyle{ n }[/math], we want to find a [math]\displaystyle{ C\subseteq\{1,2,\ldots, {m}\} }[/math] of fixed size [math]\displaystyle{ k=|C| }[/math] with the maximum coverage [math]\displaystyle{ \left|\bigcup_{i\in C}S_i\right| }[/math].
- Give a poly-time greedy algorithm for the problem. Prove that the approximation ratio is [math]\displaystyle{ 1-(1-1/k)^k\gt 1-1/e }[/math].
Problem 3
In the maximum directed cut (MAX-DICUT) problem, we are given as input a directed graph [math]\displaystyle{ G(V,E) }[/math]. The goal is to partition [math]\displaystyle{ V }[/math] into disjoint [math]\displaystyle{ S }[/math] and [math]\displaystyle{ T }[/math] so that the number of edges in [math]\displaystyle{ 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]\displaystyle{ \begin{align} \text{maximize} &&& \sum_{(u,v)\in E}y_{u,v}\\ \text{subject to} && y_{u,v} &\le x_u, & \forall (u,v)&\in E,\\ && y_{u,v} &\le 1-x_v, & \forall (u,v)&\in E,\\ && x_v &\in\{0,1\}, & \forall v&\in V,\\ && y_{u,v} &\in\{0,1\}, & \forall (u,v)&\in E. \end{align} }[/math]
Let [math]\displaystyle{ 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]\displaystyle{ v\in V }[/math], [math]\displaystyle{ \hat{x}_v=1 }[/math] independently with probability [math]\displaystyle{ 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]\displaystyle{ v\in V }[/math], [math]\displaystyle{ \hat{x}_v=1 }[/math] independently with probability [math]\displaystyle{ 1/4+x_v^*/2 }[/math]. Analyze the approximation ratio for this algorithm.
Problem 4
Recall the MAX-SAT problem and its integer program:
- [math]\displaystyle{ \begin{align} \text{maximize} &&& \sum_{j=1}^my_j\\ \text{subject to} &&& \sum_{i\in S_j^+}x_i+\sum_{i\in S_j^-}(1-x_i)\ge y_j, && 1\le j\le m,\\ &&& x_i\in\{0,1\}, && 1\le i\le n,\\ &&& y_j\in\{0,1\}, && 1\le j\le m. \end{align} }[/math]
Recall that [math]\displaystyle{ S_j^+,S_j^-\subseteq\{1,2,\ldots,n\} }[/math] are the respective sets of variables appearing positively and negatively in clause [math]\displaystyle{ j }[/math].
Let [math]\displaystyle{ x_i^*,y_j^* }[/math] denote the optimal solution to the LP-relaxation of the above integer program. In our class we learnt that if [math]\displaystyle{ \hat{x}_i }[/math] is round to 1 independently with probability [math]\displaystyle{ x_i^* }[/math], we have approximation ratio [math]\displaystyle{ 1-1/\mathrm{e} }[/math].
We consider a generalized rounding scheme such that every [math]\displaystyle{ \hat{x}_i }[/math] is round to 1 independently with probability [math]\displaystyle{ f(x_i^*) }[/math] for some function [math]\displaystyle{ f:[0,1]\to[0,1] }[/math] to be specified.
- Suppose [math]\displaystyle{ f(x) }[/math] is an arbitrary function satisfying that [math]\displaystyle{ 1-4^{-x}\le f(x)\le 4^{x-1} }[/math] for any [math]\displaystyle{ x\in[0,1] }[/math]. Show that with this rounding scheme, the approximation ratio (between the expected number of satisfied clauses and OPT) is at least [math]\displaystyle{ 3/4 }[/math].
- Derandomize this algorithm through conditional expectation and give a deterministic polynomial time algorithm with approximation ratio [math]\displaystyle{ 3/4 }[/math].
- Is it possible that for some more clever [math]\displaystyle{ f }[/math] we can do better than this? Try to justify your argument.
Problem 5
The following is the weighted version of set cover problem:
Given [math]\displaystyle{ m }[/math] subsets [math]\displaystyle{ S_1,S_2,\ldots,S_m\subseteq U }[/math], where [math]\displaystyle{ U }[/math] is a universe of size [math]\displaystyle{ n=|U| }[/math], and each subset [math]\displaystyle{ S_i }[/math] is assigned a positive weight [math]\displaystyle{ w_i\gt 0 }[/math], the goal is to find a [math]\displaystyle{ C\subseteq\{1,2,\ldots,m\} }[/math] such that [math]\displaystyle{ U=\bigcup_{i\in C}S_i }[/math] and the total weight [math]\displaystyle{ \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]\displaystyle{ \{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]\displaystyle{ U }[/math] is fully covered. Show that this can return a set cover with [math]\displaystyle{ O(\log n) }[/math] approximation ratio with probability at least [math]\displaystyle{ 0.99 }[/math].