高级算法 (Fall 2019)/Problem Set 4: Difference between revisions

Revision as of 04:54, 23 December 2019

@@ Line 3: / Line 3: @@
 == Problem 1 ==
-Modify the Karger's Contraction algorithm so that it works for the ''weighted min-cut problem''. Prove that the modified algorithm returns a weighted minimum cut with probability at least <math>\frac{2}{n(n-1)}</math>.
-The weighted min-cut problem is defined as follows.
-*'''Input''': an undirected weighted graph <math>G(V, E)</math>, where every edge <math>e \in E</math> is associated with a positive real weight <math>w_e</math>;
-*'''Output''': a cut <math>C</math> in <math>G</math> such that <math>\sum_{e \in C} w_e</math> is minimized.