Advanced Algorithms Introduction:Min-Cut and Max-Cut 尹-通Nanjing University,2022Fall
尹⼀通 Nanjing University, 2022 Fall Advanced Algorithms Introduction: Min-Cut and Max-Cut
Textbooks MIZED IMS Rajeev Motwani and Prabhakar Raghavan. Randomized Algorithms. Cambridge University Press,1995. VIJAY V.VAZIRANT Approximation Vijay Vazirani Algorithms Approximation Algorithms. Spinger-Verlag,2001
Textbooks Vijay Vazirani Approximation Algorithms. Spinger-Verlag, 2001. Rajeev Motwani and Prabhakar Raghavan. Randomized Algorithms. Cambridge University Press, 1995
References Probability and Mitzenmacher and Upfal. Computing Probability and Computing, in Alpethms and Data Anlysis 2nd Ed. and Eli Upfal The DESIGN of APPROXIMATION ALGORITHMS Williamson and Shmoys SECOND EDITION The Design of Approximation Algorithms Wiley Series in Discrete Mathematics and Optimizatlor Alon and Spencer The Probabilistic Method, Fourth Edition THE PROBABILISTIC 4th Ed. Clyorithms METHOD NOGA ALON-JOEL H.SPENCER DPV Sanjoy Dasgupta 房 Christos Papadimitriou Umesh Vaxirani Algorithms WILEY
References Mitzenmacher and Upfal. Probability and Computing, 2nd Ed. Williamson and Shmoys The Design of Approximation Algorithms Alon and Spencer The Probabilistic Method, 4th Ed. DPV Algorithms
Muhammad ibn Musa al-KhwarizmI (780-850) Advanced Algorithms
Advanced Algorithms Muḥammad ibn Mūsā al-Khwārizmī (780-850)
Minimum Cut
Minimum Cut
Min-Cut E(S,T)={uw∈E|u∈S,v∈T} Undirected graph G(V,E) Bi-partition of Vinto nonempty S and T Find a cut E(S,T)of smallest size (global min-cut) Deterministic algorithms: max-flow min-cut(duality) best upper bound (2021):m1+(1) O(.):ignore poly-logarithmic factors
Min-Cut • Undirected graph • Bi-partition of into nonempty and • Find a cut of smallest size (global min-cut) • Deterministic algorithms: • max-flow min-cut (duality) • best upper bound (2021): G(V, E) V S T E(S, T) m1+o(1) T S E(S, T) = {uv ∈ E ∣ u ∈ S, v ∈ T} : ignore poly-logarithmic factors O˜( ⋅ )
Min-Cut E(S,T)={uw∈E|u∈S,v∈T} Undirected graph G(V,E) ·Too many cuts: there are 29()bi-partitions ·(will see later）only at most O(n)min-cuts Generate a random cut that is a min-cut with large enough probability?
Min-Cut • Undirected graph • Too many cuts: • there are bi-partitions • (will see later) only at most min-cuts • Generate a random cut that is a min-cut with large enough probability? G(V, E) 2Ω(n) O(n2 ) T S E(S, T) = {uv ∈ E ∣ u ∈ S, v ∈ T}
Contraction Undirected multigraph GV,E) ·multigraph: ·allow parallel edges ·but no self-loop contract(e):e uv is an edge merges two endpoints u and v
Contraction • Undirected multigraph • multigraph: • allow parallel edges • but no self-loop • contract( ): is an edge • merges two endpoints and G(V, E) e e = uv u v e
Contraction Undirected multigraph GV,E) 。multigraph: ·allow parallel edges ·but no self-loop contract(e):e uv is an edge merges two endpoints u and v
Contraction • Undirected multigraph • multigraph: • allow parallel edges • but no self-loop • contract( ): is an edge • merges two endpoints and G(V, E) e e = uv u v
Karger's Min-Cut Algorithm ·multigraph G(V,E) Karger's Algorithm: whileV>2 do: pick random e∈E; contract(e); return remaining edges; random:uniformly and independently at random
Karger’s Algorithm: while do: pick random ; contract ; return remaining edges; |V| > 2 e ∈ E (e) • multigraph G(V, E) Karger’s Min-Cut Algorithm random: uniformly and independently at random