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

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

Problem 1

For any [math]\displaystyle{ \alpha\ge 1 }[/math], a cut [math]\displaystyle{ C }[/math] in an undirected (multi)graph [math]\displaystyle{ G(V,E) }[/math] is called an [math]\displaystyle{ \alpha }[/math]-min-cut if [math]\displaystyle{ |C|\le\alpha|C^*| }[/math] where [math]\displaystyle{ C^* }[/math] is a min-cut in [math]\displaystyle{ G }[/math].

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

Problem 2

Let [math]\displaystyle{ G(V,E) }[/math] be an undirected graph with positive edge weights [math]\displaystyle{ w:E\to\mathbb{Z}^+ }[/math]. Given a partition of [math]\displaystyle{ V }[/math] into [math]\displaystyle{ k }[/math] disjoint subsets [math]\displaystyle{ S_1,S_2,\ldots,S_k }[/math], we define

[math]\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) }[/math]

as the cost of the [math]\displaystyle{ k }[/math]-cut [math]\displaystyle{ \{S_1,S_2,\ldots,S_k\} }[/math]. Our goal is to find a [math]\displaystyle{ k }[/math]-cut with maximum cost.

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

Problem 3

Given [math]\displaystyle{ m }[/math] subsets [math]\displaystyle{ S_1,S_2,\ldots, S_m\subseteq U }[/math] of a universe [math]\displaystyle{ U }[/math] of size [math]\displaystyle{ n }[/math], we want to find a [math]\displaystyle{ C\subseteq\{1,2,\ldots, {\color{red}m}\} }[/math] of fixed size [math]\displaystyle{ k=|C| }[/math] with the maximum coverage [math]\displaystyle{ \left|\bigcup_{i\in C}S_i\right| }[/math].

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

Problem 4

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

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

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

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

• Prove that the approximation ratio is 2.

Problem 5

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

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

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

   [math]\displaystyle{ \forall v\in V, \sum_{e\ni v}(1-1/n)^{-|e|}2^{-|e|+1}\le \frac{1}{n} }[/math].

   • Prove that [math]\displaystyle{ H }[/math] has property B.
   • Describe how to use Moser-Tardos random solver to find a proper 2-coloring of [math]\displaystyle{ H }[/math]. Give an upper bound on the expected running time.