# 高级算法 (Fall 2017)/Problem Set 3

Jump to: navigation, search

## Problem 1

Consider the following optimization problem.

Instance: ${\displaystyle n}$ positive integers ${\displaystyle x_{1}.
Find two disjoint nonempty subsets ${\displaystyle A,B\subset \{1,2,\ldots ,n\}}$ with ${\displaystyle \sum _{i\in A}x_{i}\geq \sum _{i\in B}x_{i}}$, such that the ratio ${\displaystyle {\frac {\sum _{i\in A}x_{i}}{\sum _{i\in B}x_{i}}}}$ 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 ${\displaystyle G(V,E)}$. The goal is to partition ${\displaystyle V}$ into disjoint ${\displaystyle S}$ and ${\displaystyle T}$ so that the number of edges in ${\displaystyle E(S,T)=\{(u,v)\in E\mid u\in S,v\in T\}}$ is maximized. The following is the integer program for MAX-DICUT:

{\displaystyle {\begin{aligned}{\text{maximize}}&&&\sum _{(u,v)\in E}y_{u,v}\\{\text{subject to}}&&y_{u,v}&\leq x_{u},&\forall (u,v)&\in E,\\&&y_{u,v}&\leq 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{aligned}}}

Let ${\displaystyle x_{v}^{*},y_{u,v}^{*}}$ denote the optimal solution to the LP-relaxation of the above integer program.

• Apply the randomized rounding such that for every ${\displaystyle v\in V}$, ${\displaystyle {\hat {x}}_{v}=1}$ independently with probability ${\displaystyle x_{v}^{*}}$. Analyze the approximation ratio (between the expected size of the random cut and OPT).
• Apply another randomized rounding such that for every ${\displaystyle v\in V}$, ${\displaystyle {\hat {x}}_{v}=1}$ independently with probability ${\displaystyle 1/4+x_{v}^{*}/2}$. Analyze the approximation ratio for this algorithm.

## Problem 3

Recall the MAX-SAT problem and its integer program:

{\displaystyle {\begin{aligned}{\text{maximize}}&&&\sum _{j=1}^{m}y_{j}\\{\text{subject to}}&&&\sum _{i\in S_{j}^{+}}x_{i}+\sum _{i\in S_{j}^{-}}(1-x_{i})\geq y_{j},&&1\leq j\leq m,\\&&&x_{i}\in \{0,1\},&&1\leq i\leq n,\\&&&y_{j}\in \{0,1\},&&1\leq j\leq m.\end{aligned}}}

Recall that ${\displaystyle S_{j}^{+},S_{j}^{-}\subseteq \{1,2,\ldots ,n\}}$ are the respective sets of variables appearing positively and negatively in clause ${\displaystyle j}$.

Let ${\displaystyle x_{i}^{*},y_{j}^{*}}$ denote the optimal solution to the LP-relaxation of the above integer program. In our class we learnt that if ${\displaystyle {\hat {x}}_{i}}$ is round to 1 independently with probability ${\displaystyle x_{i}^{*}}$, we have approximation ratio ${\displaystyle 1-1/\mathrm {e} }$.

We consider a generalized rounding scheme such that every ${\displaystyle {\hat {x}}_{i}}$ is round to 1 independently with probability ${\displaystyle f(x_{i}^{*})}$ for some function ${\displaystyle f:[0,1]\to [0,1]}$ to be specified.

• Suppose ${\displaystyle f(x)}$ is an arbitrary function satisfying that ${\displaystyle 1-4^{-x}\leq f(x)\leq 4^{x-1}}$ for any ${\displaystyle x\in [0,1]}$. Show that with this rounding scheme, the approximation ratio (between the expected number of satisfied clauses and OPT) is at least ${\displaystyle 3/4}$.
• Derandomize this algorithm through conditional expectation and give a deterministic polynomial time algorithm with approximation ratio ${\displaystyle 3/4}$.
• Is it possible that for some more clever ${\displaystyle f}$ we can do better than this? Try to justify your argument.

## Problem 4

The following is the weighted version of set cover problem:

Given ${\displaystyle m}$ subsets ${\displaystyle S_{1},S_{2},\ldots ,S_{m}\subseteq U}$, where ${\displaystyle U}$ is a universe of size ${\displaystyle n=|U|}$, and each subset ${\displaystyle S_{i}}$ is assigned a positive weight ${\displaystyle w_{i}>0}$, the goal is to find a ${\displaystyle C\subseteq \{1,2,\ldots ,m\}}$ such that ${\displaystyle U=\bigcup _{i\in C}S_{i}}$ and the total weight ${\displaystyle \sum _{I\in C}w_{i}}$ 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 ${\displaystyle \{0,1\}}$ with the probability of the fractional value itself; and repeatedly apply this process to the variables rounded to 0 in previous iterations until ${\displaystyle U}$ is fully covered. Show that this can return a set cover with ${\displaystyle O(\log n)}$ approximation ratio with probability at least ${\displaystyle 0.99}$.

## Problem 5

Recall that the instance of set cover problem is a collection of ${\displaystyle m}$ subsets ${\displaystyle S_{1},S_{2},\ldots ,S_{m}\subseteq U}$, where ${\displaystyle U}$ is a universe of size ${\displaystyle n=|U|}$. The goal is to find the smallest ${\displaystyle C\subseteq \{1,2,\ldots ,m\}}$ such that ${\displaystyle U=\bigcup _{i\in C}S_{i}}$. The frequency ${\displaystyle f}$ is defined to be ${\displaystyle \max _{x\in U}|\{i\mid x\in S_{i}\}|}$.

• 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 ${\displaystyle f}$.