A New Regularity Lemma and Faster Approximation Algorithms for Low Threshold Rank Graphs

DOI10.1007/978-3-642-40328-6_22zbMath1337.68294arXiv1212.1831OpenAlexW2808390993MaRDI QIDQ2851865

Luca Trevisan, Shayan Oveis Gharan

Publication date: 4 October 2013

Published in: Theory of Computing, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1212.1831

zbMATH Keywords

approximation algorithmmaximum cutregularity lemmaexpander graphslow threshold rank graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (5)

An experimental evaluation of the best-of-many Christofides' algorithm for the traveling salesman problem ⋮ A unified view of graph regularity via matrix decompositions ⋮ Unnamed Item ⋮ Multi-way spectral partitioning and higher-order cheeger inequalities ⋮ Spectral graph theory via higher order eigenvalues and applications to the analysis of random walks

Cites Work

• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming

This page was built for publication: A New Regularity Lemma and Faster Approximation Algorithms for Low Threshold Rank Graphs