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

From TCS Wiki
Jump to navigation Jump to search
imported>Etone
No edit summary
imported>Etone
 
(16 intermediate revisions by the same user not shown)
Line 1: Line 1:
每道题目的解答都要有<font color="red" >完整的解题过程</font>。中英文不限。
== 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 11: 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 19: 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>.
== Problem 4==
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 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
    assign the next ''available'' job on the list to the machine;
Here a job <math>k</math> is available if all jobs <math>j\prec k</math> have already been completely processed.
* Prove that the approximation ratio is 2.
== Problem 5 ==
For a '''hypergraph''' <math>H(V,E)</math> with vertex set <math>V</math>, every '''hyperedge''' <math>e\in E</math> is a subset <math>e\subset V</math> of vertices, not necessarily of size 2. A hypergraph <math>H(V,E)</math> is '''<math>k</math>-uniform''' if every hyperedge <math>e\in V</math> is of size <math>k=|e|</math>.
A hypergraph <math>H(V,E)</math> is said to have '''property B''' (named after Bernstein) if <math>H</math> is 2-coloable; that is, if there is a '''proper 2-coloring''' <math>f:V\to\{{\color{red}R},{\color{blue}B}\}</math> which assigns each vertex one of the two colors <font color=red>Red</font> or <font color=blue>Blue</font>, such that none of the hyperedge is ''monochromatic''.
# 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.
#*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 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 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
#:<math>\forall v\in V, \sum_{e\ni v}(1-1/n)^{-|e|}2^{-|e|+1}\le \frac{1}{n}</math>.
#*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.

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.