# 随机算法 \ 高级算法 (Fall 2016)/Problem Set 1

每道题目的解答都要有完整的解题过程。中英文不限。


## Problem 1

For any ${\displaystyle \alpha \geq 1}$, a cut ${\displaystyle C}$ in an undirected (multi)graph ${\displaystyle G(V,E)}$ is called an ${\displaystyle \alpha }$-min-cut if ${\displaystyle |C|\leq \alpha |C^{*}|}$ where ${\displaystyle C^{*}}$ is a min-cut in ${\displaystyle G}$.

1. Give a lower bound to the probability that Karger's Random Contraction algorithm returns an ${\displaystyle \alpha }$-min-cut in a graph ${\displaystyle G(V,E)}$ of ${\displaystyle n}$ vertices.
2. Use the above bound to estimate the number of distinct ${\displaystyle \alpha }$-min cuts in ${\displaystyle G}$.

## Problem 2

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 3

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 ,{\color {red}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 4

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.

## Problem 5

For a hypergraph ${\displaystyle H(V,E)}$ with vertex set ${\displaystyle V}$, every hyperedge ${\displaystyle e\in E}$ is a subset ${\displaystyle e\subset V}$ of vertices, not necessarily of size 2. A hypergraph ${\displaystyle H(V,E)}$ is ${\displaystyle k}$-uniform if every hyperedge ${\displaystyle e\in V}$ is of size ${\displaystyle k=|e|}$.

A hypergraph ${\displaystyle H(V,E)}$ is said to have property B (named after Bernstein) if ${\displaystyle H}$ is 2-coloable; that is, if there is a proper 2-coloring ${\displaystyle f:V\to \{{\color {red}R},{\color {blue}B}\}}$ which assigns each vertex one of the two colors Red or Blue, such that none of the hyperedge is monochromatic.

1. Let ${\displaystyle H(V,E)}$ be a ${\displaystyle k}$-uniform hypergraph in which every hyperedge ${\displaystyle e\in E}$ shares vertices with at most ${\displaystyle d}$ other hyperedges.
• Prove that if ${\displaystyle 2\mathrm {e} \cdot (d+1)\leq 2^{k}}$, then ${\displaystyle H}$ has property B.
• Describe how to use Moser's recursive Fix algorithm to find a proper 2-coloring of ${\displaystyle H}$. Give the pseudocode. Prove the condition in in terms of ${\displaystyle d}$ and ${\displaystyle k}$ under which the algorithm can find a 2-coloring of ${\displaystyle H}$ with high probability.
• Describe how to use Moser-Tardos random solver to find a proper 2-coloring of ${\displaystyle H}$. Give the pseudocode. Prove the condition in in terms of ${\displaystyle d}$ and ${\displaystyle k}$ under which the algorithm can find a 2-coloring of ${\displaystyle H}$ within bounded expected time. Give an upper bound on the expected running time.
2. Let ${\displaystyle H(V,E)}$ be a hypergraph (not necessarily uniform) with at least ${\displaystyle n\geq 2}$ vertices satisfying that
${\displaystyle \forall v\in V,\sum _{e\ni v}(1-1/n)^{-|e|}2^{-|e|+1}\leq {\frac {1}{n}}}$.
• Prove that ${\displaystyle H}$ has property B.
• Describe how to use Moser-Tardos random solver to find a proper 2-coloring of ${\displaystyle H}$. Give an upper bound on the expected running time.