Comparing the Theory and Practice of Spectral Algorithms to Combinatorial Flow Algorithms for ...

on YouTube ↗59m

" summary

Compares spectral algorithms and combinatorial flow algorithms for graph partitioning and related cut problems, discussing their theoretical guarantees versus empirical behavior. Examines specific algorithms (spectral methods and flow-based combinatorial algorithms), the problem of finding low-conductance/low-cut partitions in graphs, and contrasts performance, approximation quality, and practical considerations.

AI-written summary · about

" chapters (14)

1. 0:00Intro
2. 2:16A generalization: quantity normalized cut
3. 3:29An intuitive clustering criterion
4. 10:04Two terms expressions and the Rayleigh ratio (Lemma 3.1, [H13])
5. 12:27The combinatorial versus the spectral continuous relaxations
6. 19:42It works because the problem can be formulated as "monotone integer program" Theorem
7. 27:18Scaling arcs weights
8. 28:07The Simplified equivalent graph
9. 28:57Solving the parametric min st cut
10. 34:21Comparison between NC' and the spectral method
11. 37:47Empirical testing for the general problems
12. 39:18Scalability of NC' versus the spectral algorithm (Shi)
13. 41:57A comparison of NC values of NC' with the sweep spectral algorithm
14. 51:02Conclusions

" related talks

• 29mSampling Algorithms for Combinatorial Pure ExplorationAnupam Gupta · Optimization, Statistics and Uncertainty
• 12mToward Nearly-Zero-Error Sketching via Compressive SensingGong Zhang, Rui Zhang, Yungang Bao, Xiang Chen, Qun Huang, Yanwei Xu, Siyuan Sheng · NSDI ’21
• 33mLearning the Best Agorithm for Max-Cut, Clustering, and Other​ ​Partitioning ProblemsVaishnavh Nagarajan · Learning, Algorithm Design and Beyond Worst-Case Analysis
• 01h 11mStatistical Physics and Computation in High DimensionFlorent Krzakala, Lenka Zdeborova · Probability, Geometry, and Computation in High Dimensions Boot Camp (Simons Institute, Fall 2020)
• 49mGeneralized Cheeger Inequalities and Constrained ClusteringIoannis Koutis · Fast Algorithms via Spectral Methods 2014
• 44mScalable Algorithmic Primitives for Data ScienceRichard Peng · Randomized Numerical Linear Algebra and Applications 2018
• 29mSpectrally Robust Graph IsomorphismYiannis Koutis · Randomized Numerical Linear Algebra and Applications 2018
• 01h 12mA Brief Introduction to Algorithms, Game Theory and Risk-Averse Decision MakingEvdokia Nikolova · Real-Time Decision Making Boot Camp, Spring 2018