# 高级算法 (Fall 2018)/Problem Set 4

Note: in this problem set, 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 $G(V,E)$ be an undirected graph with positive edge weights $w:E\to \mathbb {Z} ^{+}$ . Given a partition of $V$ into $k$ disjoint subsets $S_{1},S_{2},\ldots ,S_{k}$ , we define

$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)$ as the cost of the $k$ -cut $\{S_{1},S_{2},\ldots ,S_{k}\}$ . Our goal is to find a $k$ -cut with maximum cost.

1. Give a poly-time greedy algorithm for finding the weighted max $k$ -cut. Prove that the approximation ratio is $(1-1/k)$ .
2. 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 $V$ into disjoint $S_{0},S_{1}$ ;
while (true) do
if $\exists i\in \{0,1\}$ and $v\in S_{i}$ such that (______________)
then $v$ leaves $S_{i}$ and joins $S_{1-i}$ ;
continue;
end if
break;
end


## Problem 2

Given $m$ subsets $S_{1},S_{2},\ldots ,S_{m}\subseteq U$ of a universe $U$ of size $n$ , we want to find a $C\subseteq \{1,2,\ldots ,{m}\}$ of fixed size $k=|C|$ with the maximum coverage $\left|\bigcup _{i\in C}S_{i}\right|$ .

• Give a poly-time greedy algorithm for the problem. Prove that the approximation ratio is $1-(1-1/k)^{k}>1-1/e$ .

## Problem 3

In the maximum directed cut (MAX-DICUT) problem, we are given as input a directed graph $G(V,E)$ . The goal is to partition $V$ into disjoint $S$ and $T$ so that the number of edges in $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:

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

## Problem 4

Recall the MAX-SAT problem and its integer program:

{\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 $S_{j}^{+},S_{j}^{-}\subseteq \{1,2,\ldots ,n\}$ are the respective sets of variables appearing positively and negatively in clause $j$ .

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

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

• Suppose $f(x)$ is an arbitrary function satisfying that $1-4^{-x}\leq f(x)\leq 4^{x-1}$ for any $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 $3/4$ .
• Derandomize this algorithm through conditional expectation and give a deterministic polynomial time algorithm with approximation ratio $3/4$ .
• Is it possible that for some more clever $f$ we can do better than this? Try to justify your argument.

## Problem 5

The following is the weighted version of set cover problem:

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