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

From TCS Wiki
Jump to navigation Jump to search
imported>Etone
imported>Etone
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.
* 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.

Revision as of 14:00, 20 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.