高级算法 (Fall 2020)/Problem Set 3

Problem 1

Given $m$ subsets $S_1,S_2,\dots ,S_m\subseteq U$ of a universe $U$ of size $n$, we want to find a $C\subseteq \{1,2,\dots ,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 2

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{array}{rlrl}\text{maximize}& & & \sum _{(u,v)\in E}{y}_{u,v}\\ \text{subject to}& & y_{u,v}& \le x_u,& \mathrm{\forall }(u,v)& \in E,\\ & & y_{u,v}& \le 1-x_v,& \mathrm{\forall }(u,v)& \in E,\\ & & x_v& \in \{0,1\},& \mathrm{\forall }v& \in V,\\ & & y_{u,v}& \in \{0,1\},& \mathrm{\forall }(u,v)& \in E.\end{array}$

Let $x_v^{\ast },y_{u,v}^{\ast }$ 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^{\ast }$. 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^{\ast }/2$. Analyze the approximation ratio for this algorithm.

Problem 3

Recall the MAX-SAT problem and its integer program:

$\begin{array}{rlrl}\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)\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{array}$

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

Let $x_i^{\ast },y_j^{\ast }$ 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^{\ast }$, 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^{\ast })$ for some function $f:[0,1]\to [0,1]$ to be specified.

• Suppose $f(x)$ is an arbitrary function satisfying that $1-4^{-x}\le f(x)\le 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 4

The following is the weighted version of set cover problem:

Given $m$ subsets $S_1,S_2,\dots ,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,\dots ,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$.

Problem 5

Consider the following greedy algorithm for the knapsack problem, which has been briefly mentioned in class:

Sort all items according to the ratio $r_i=v_i/w_i$ so that $r_1\ge r_2\ge \dots \ge r_n$; for $i=1,2,...,n$ item $i$ joins $S$ if the resulting total weight $\le B$;

• Show that the approximation ratio of this algorithm can be arbitrarily bad. Formally, given an arbitrary constant $ϵ\in (0,1)$, construct an instance that the solution of this algorithm $SOL$ is less than $(1-ϵ)OPT$.
• Consider the following modification to this algorithm. Let the sorted order of objects be $a_1,...,a_n$. Find the lowest $k$ such that the size of the first $k$ objects exceeds $B$. Now, pick the more valuable of $\{a_1,...,a_{k-1}\}$ and $\{a_k\}$ (we have assumed that the size of each object is at most $B$). Show that this algorithm achieves an approximation ratio of $1/2$.