Cut-Equivalent Trees are Optimal for Min-Cut Queries
Offered By: IEEE via YouTube
Course Description
Overview
Explore a 24-minute IEEE conference talk on cut-equivalent trees and their optimality for min-cut queries. Delve into previous algorithms for constructing Gomory-Hu trees, min-cut data structures, and the equivalence between min-cut data structures and cut-equivalent trees. Learn about the Gomory-Hu algorithm description, tournament expansion, and the challenges of designing fast approximation algorithms. Gain insights from speakers Amir Abboud, Robert Krauthgamer, and Ohad Trabelsi as they discuss their findings and present approximation ideas for this complex graph theory topic.
Syllabus
Introduction
Previous Algorithms for constructing GH Trees
Min-Cut Data-Structure
Equivalence Between Min-Cut Data Structure and Cut-Equivalent Tree
First Result:Yes!
Corollaries
Gomory-Hu Algorithm Description
Tournament
Expansion
Gomory-Hu Fails Using Approx.
Issues with Designing Fast Approx. Algorithms
Approximation Idea
Taught by
IEEE FOCS: Foundations of Computer Science
Tags
Related Courses
An Improved Exponential-Time Approximation Algorithm for Fully-Alternating Games Against NatureIEEE via YouTube Computation in the Brain Tutorial - Part 2
IEEE via YouTube Computation in the Brain - Part 1
IEEE via YouTube Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model
IEEE via YouTube Cookbook Lower Bounds for Statistical Inference in Distributed and Constrained Settings - Part 1
IEEE via YouTube