View source for 随机算法 \ 高级算法 (Fall 2016)/Problem Set 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>. 

# 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.
# Use the above bound to estimate the number of distinct <math>\alpha</math>-min cuts in <math>G</math>.

== Problem 2==
Let <math>G(V,E)</math> be an undirected graph with positive edge weights <math>w:E\to\mathbb{Z}^+</math>. Given a partition of <math>V</math> into <math>k</math> disjoint subsets <math>S_1,S_2,\ldots,S_k</math>, we define
:<math>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>k</math>-cut''' <math>\{S_1,S_2,\ldots,S_k\}</math>. Our goal is to find a <math>k</math>-cut with maximum cost. 
# Give a 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).
 start with an arbitrary bipartition of <math>V</math> into disjoint <math>S_0,S_1</math>;
 while (true) do
    if <math>\exists v\in S_i</math> for an <math>i\in\{0,1\}</math> such that <font color=red>(                  )</font>
       then <math>v</math> leaves <math>S_i</math> and joins <math>S_{1-i}</math>;
       continue;
    end if
    break;
 end

== Problem 2==
A '''matching''' of an undirected graph <math>G(V,E)</math> is a set <math>M\subseteq E</math> of edges such that <math>\forall e_1,e_2\in M, e_1\cap e_2=\emptyset</math>. A matching  <math>M\subseteq E</math> is ''maximal'' if <math>\forall e\in E\setminus M</math>, <math>M\cup\{e\}</math> is not a matching. A maximal matching <math>M\subseteq E</math> is ''minimum'' if <math>|M|</math> is smallest among all maximal matchings in <math>G(V,E)</math>. A '''minimum maximal matching''' must also be a '''minimum [https://en.wikipedia.org/wiki/Edge_dominating_set edge dominating set]'''. Finding a minimum maximal matching is '''NP-hard'''.