View source for 随机算法 \ 高级算法 (Fall 2016)/Problem Set 2

每道题目的解答都要有<font color="red" >完整的解题过程</font>。中英文不限。


== Problem 1==
Consider the following optimization problem.
:'''Instance''': <math>n</math> positive integers <math>x_1<x_2<\cdots <x_n</math>.
:Find two ''disjoint'' nonempty subsets <math>A,B\subset\{1,2,\ldots,n\}</math> with <math>\sum_{i\in A}x_i\ge \sum_{i\in B}x_i</math>, such that the ratio <math>\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>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>