YoVDO

Weighted Min-Cut - Sequential, Cut-Query and Streaming Algorithms

Offered By: Association for Computing Machinery (ACM) via YouTube

Tags

Algorithm Design Courses Graph Theory Courses

Course Description

Overview

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.

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)

Related Courses

Natural Language Processing
Columbia University via Coursera
Intro to Algorithms
Udacity
Conception et mise en œuvre d'algorithmes.
École Polytechnique via Coursera
Paradigms of Computer Programming
Université catholique de Louvain via edX
Data Structures and Algorithm Design Part I | 数据结构与算法设计(上)
Tsinghua University via edX