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

From TCS Wiki
Jump to navigation Jump to search
imported>Etone
imported>Etone
 
(7 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 32: Line 32:
We consider minimum makespan scheduling on parallel identical machines when jobs are subject to '''precedence constraints'''.  
We consider minimum makespan scheduling on parallel identical machines when jobs are subject to '''precedence constraints'''.  


We still want to schedule <math>n</math> jobs <math>j=1,2,\ldots, n</math> on <math>m</math> identical machines, where job <math>j</math> has  processing time <math>p_j</math>. But now a partial order <math>\preceq</math> is defined on jobs, so that if <math>j\prec k</math> then job <math>j</math> must be completely finished before job <math>k</math> begins. The following is a variant of the ''List'' algorithm for this problem.
We still want to schedule <math>n</math> jobs <math>j=1,2,\ldots, n</math> on <math>m</math> identical machines, where job <math>j</math> has  processing time <math>p_j</math>. But now a partial order <math>\preceq</math> is defined on jobs, so that if <math>j\prec k</math> then job <math>j</math> must be completely finished before job <math>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>n</math> jobs with processing times <math>p_1,p_2,\ldots, p_n</math>.


  whenever a machine becomes idle
  whenever a machine becomes idle
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.