2016/07/04 by Thomas Rothvoß, Rothvoss, Thomas
Engineering · #Advanced Numerical Analysis Techniques #Advanced Surface Polishing Techniques #Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Industrial Vision Systems and Defect Detection
paper · pdf · doi:10.48550/arxiv.1607.00854
openalex publication_date 2016/07/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
One of the landmarks in approximation algorithms is the O(√(log n))-approximation algorithm for the Uniform Sparsest Cut problem by Arora, Rao and Vazirani from 2004. The algorithm is based on a semidefinite program that finds an embedding of the nodes respecting the triangle inequality. Their core argument shows that a random hyperplane approach will find two large sets of Θ(n) many nodes each that have a distance of Θ(1/√(log n)) to each other if measured in terms of ‖⋅ ‖22. Here we give a detailed set of lecture notes describing the algorithm. For the proof of the Structure Theorem we use a cleaner argument based on expected maxima over k-neighborhoods that significantly simplifies the analysis.