随机算法 \ 高级算法 (Fall 2016)/Problem Set 1: Difference between revisions

From TCS Wiki
Jump to navigation Jump to search
imported>Etone
imported>Etone
 
(6 intermediate revisions by the same user not shown)
Line 3: Line 3:


== Problem 1==
== Problem 1==
For any <math>\alpha\ge 1</math>, a cut <math>C</math> in an undirected (multi)graph <math>G(V,E)</math>is called an <math>\alpha</math>-min-cut if <math>|C|\le\alpha|C^*|</math> where <math>C^*</math> is a min-cut in <math>G</math>.  
For any <math>\alpha\ge 1</math>, a cut <math>C</math> in an undirected (multi)graph <math>G(V,E)</math> is called an <math>\alpha</math>-min-cut if <math>|C|\le\alpha|C^*|</math> where <math>C^*</math> is a min-cut in <math>G</math>.  


# Give a lower bound to the probability that Karger's Random Contraction algorithm returns an <math>\alpha</math>-min-cut in a graph <math>G(V,E)</math> of <math>n</math> vertices.
# Give a lower bound to the probability that Karger's Random Contraction algorithm returns an <math>\alpha</math>-min-cut in a graph <math>G(V,E)</math> of <math>n</math> vertices.
Line 14: Line 14:
# Give a poly-time greedy algorithm for finding the weighted max <math>k</math>-cut. Prove that the approximation ratio is <math>(1-1/k)</math>.
# Give a poly-time greedy algorithm for finding the weighted max <math>k</math>-cut. Prove that the approximation ratio is <math>(1-1/k)</math>.
# Consider the following local search algorithm for the weighted max cut (max 2-cut).
# 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>V</math> into disjoint <math>S_0,S_1</math>;
  start with an arbitrary bipartition of <math>V</math> into disjoint <math>S_0,S_1</math>;
  while (true) do
  while (true) do
Line 22: Line 23:
     break;
     break;
  end
  end
:Fill in the blank parenthesis. Give an analysis of the running time of the algorithm. And prove that the approximation ratio is 0.5.


== Problem 3==
== Problem 3==
Given <math>m</math> subsets <math>S_1,S_2,\ldots, S_m\subseteq U</math> of a universe <math>U</math> of size <math>n</math>, we want to find a <math>C\subseteq\{1,2,\ldots, n\}</math> of fixed size <math>k=|C|</math> with the maximum '''coverage''' <math>\left|\bigcup_{i\in C}S_i\right|</math>.
Given <math>m</math> subsets <math>S_1,S_2,\ldots, S_m\subseteq U</math> of a universe <math>U</math> of size <math>n</math>, we want to find a <math>C\subseteq\{1,2,\ldots, {\color{red}m}\}</math> of fixed size <math>k=|C|</math> with the maximum '''coverage''' <math>\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>1-(1-1/k)^k>1-1/e</math>.
* Give a poly-time greedy algorithm for the problem. Prove that the approximation ratio is <math>1-(1-1/k)^k>1-1/e</math>.
Line 47: Line 47:


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

Latest revision as of 04:53, 12 October 2016

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


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.