随机算法 \ 高级算法 (Fall 2016)/Problem Set 2: Difference between revisions

From TCS Wiki
Jump to navigation Jump to search
imported>Etone
imported>Etone
 
(6 intermediate revisions by the same user not shown)
Line 19: Line 19:
\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.
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 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.
* 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 3==
== Problem 3==
Recall the MAX-SAT problem and its integer program.
Recall the MAX-SAT problem and its integer program:
:::<math>
:::<math>
\begin{align}
\begin{align}
\text{maximize} &&& \sum_{j=1}^my_j\\
\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), && 1\le j\le m,\\
\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,\\
&&& x_i\in\{0,1\}, && 1\le i\le n,\\
&&& y_j\in\{0,1\}, && 1\le j\le m.
&&& y_j\in\{0,1\}, && 1\le j\le m.
\end{align}
\end{align}
</math>
</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>.
* Is it possible that for some more clever <math>f</math> we can do better than this? Try to justify your argument.
== Problem 4==
Recall that the instance of '''set cover''' problem is a collection of  <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>. The goal is to find the smallest <math>C\subseteq\{1,2,\ldots,m\}</math> such that <math>U=\bigcup_{i\in C}S_i</math>. The frequency <math>f</math> is defined to be <math>\max_{x\in U}|\{i\mid x\in S_i\}|</math>.
* Give the primal integer program for set cover, its LP-relaxation and the dual LP.
* Describe the complementary slackness conditions for the problem.
* Give a primal-dual algorithm for the problem. Present the algorithm in the language of primal-dual scheme (alternatively raising variables for the LPs). Analyze the approximation ratio in terms of the frequency <math>f</math>.

Latest revision as of 02:57, 21 October 2016

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


Problem 1

Consider the following optimization problem.

Instance: [math]\displaystyle{ n }[/math] positive integers [math]\displaystyle{ x_1\lt x_2\lt \cdots \lt x_n }[/math].
Find two disjoint nonempty subsets [math]\displaystyle{ A,B\subset\{1,2,\ldots,n\} }[/math] with [math]\displaystyle{ \sum_{i\in A}x_i\ge \sum_{i\in B}x_i }[/math], such that the ratio [math]\displaystyle{ \frac{\sum_{i\in A}x_i}{\sum_{i\in B}x_i} }[/math] is minimized.

Give a pseudo-polynomial time algorithm for the problem, and then give an FPTAS for the problem based on the pseudo-polynomial time algorithm.

Problem 2

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 3

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].
  • Is it possible that for some more clever [math]\displaystyle{ f }[/math] we can do better than this? Try to justify your argument.

Problem 4

Recall that the instance of set cover problem is a collection of [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]. The goal is to find the smallest [math]\displaystyle{ C\subseteq\{1,2,\ldots,m\} }[/math] such that [math]\displaystyle{ U=\bigcup_{i\in C}S_i }[/math]. The frequency [math]\displaystyle{ f }[/math] is defined to be [math]\displaystyle{ \max_{x\in U}|\{i\mid x\in S_i\}| }[/math].

  • Give the primal integer program for set cover, its LP-relaxation and the dual LP.
  • Describe the complementary slackness conditions for the problem.
  • Give a primal-dual algorithm for the problem. Present the algorithm in the language of primal-dual scheme (alternatively raising variables for the LPs). Analyze the approximation ratio in terms of the frequency [math]\displaystyle{ f }[/math].