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

## Problem 1

Let ${\displaystyle G(V,E)}$ be an undirected graph with positive edge weights ${\displaystyle w:E\to \mathbb {Z} ^{+}}$. Given a partition of ${\displaystyle V}$ into ${\displaystyle k}$ disjoint subsets ${\displaystyle S_{1},S_{2},\ldots ,S_{k}}$, we define

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

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


## Problem 2

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

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

## Problem 3

We consider minimum makespan scheduling on parallel identical machines when jobs are subject to precedence constraints.

We still want to schedule ${\displaystyle n}$ jobs ${\displaystyle j=1,2,\ldots ,n}$ on ${\displaystyle m}$ identical machines, where job ${\displaystyle j}$ has processing time ${\displaystyle p_{j}}$. But now a partial order ${\displaystyle \preceq }$ is defined on jobs, so that if ${\displaystyle j\prec k}$ then job ${\displaystyle j}$ must be completely finished before job ${\displaystyle k}$ begins. The following is a variant of the List algorithm for this problem: we still assume that the input is a list of ${\displaystyle n}$ jobs with processing times ${\displaystyle p_{1},p_{2},\ldots ,p_{n}}$.

whenever a machine becomes idle
assign the next available job on the list to the machine;


Here a job ${\displaystyle k}$ is available if all jobs ${\displaystyle j\prec k}$ have already been completely processed.

• Prove that the approximation ratio is 2.