Explore cutting-edge algorithms for solving the weighted min-cut problem in this 20-minute conference talk presented at the Association for Computing Machinery (ACM). Delve into sequential, cut-query, and streaming algorithms, examining the state-of-the-art approaches in each model. Learn about the global mincut problem, 2-respecting cuts, and the matrix min-entry problem. Discover a novel schematic algorithm that works across different models, providing a unified approach to solving weighted min-cut problems. Gain insights into the implementation details for various scenarios and consider open problems in this field of study.
Weighted Min-Cut - Sequential, Cut-Query and Streaming Algorithms
Association for Computing Machinery (ACM) via YouTube
Overview
Syllabus
Intro
The (global) mincut problem
State-of-the-art (Sequential)
Cut-query model
State-of-the-art (Cut-query & Streaming)
Bottleneck?
Our result: One (schematic) algorithm that works across models
2-respecting cut
Matrix min-entry problem
Solution for matrix min-entry
All results follow from one schematic algoritma (with different implementation details)
Open problems
Taught by
Association for Computing Machinery (ACM)
