Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut
From MaRDI portal
Publication:5009512
DOI10.4230/LIPIcs.APPROX-RANDOM.2018.20OpenAlexW2888878694MaRDI QIDQ5009512
Pasin Manurangsi, Luca Trevisan
Publication date: 4 August 2021
Full work available at URL: https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2018.20
Related Items (2)
Mean isoperimetry with control on outliers: exact and approximation algorithms ⋮ New tools and connections for exponential-time approximation
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms
- Ramsey numbers and an approximation algorithm for the vertex cover problem
- On the hardness of approximating minimum vertex cover
- An improved approximation ratio for the minimum linear arrangement problem
- \(\ell ^2_2\) spreading metrics for vertex ordering problems
- Which problems have strongly exponential complexity?
- On the hardness of approximating Multicut and Sparsest-Cut
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- An Explicit Equivalent Positive Semidefinite Program for Nonlinear 0-1 Programs
- Graph expansion and the unique games conjecture
- Approximation schemes via Sherali-Adams hierarchy for dense constraint satisfaction problems and assignment problems
- Local Global Tradeoffs in Metric Embeddings
- Improved Approximation Algorithms for the Vertex Cover Problem in Graphs and Hypergraphs
- Proof verification and the hardness of approximation problems
- Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
- Subexponential Algorithms for Unique Games and Related Problems
- Relations between average case complexity and approximation complexity
- On the power of unique 2-prover 1-round games
- Two-query PCP with subconstant error
- Euclidean distortion and the sparsest cut
- O(√log n) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems
- Improved Approximation Algorithms for Minimum Weight Vertex Separators
- Probabilistic checking of proofs
- Sum-of-squares proofs and the quest toward optimal algorithms
- Sum of squares lower bounds for refuting any CSP
- On independent sets, 2-to-2 games, and Grassmann graphs
- Optimal Long Code Test with One Free Bit
- Towards a proof of the 2-to-1 games conjecture?
- On non-optimally expanding sets in Grassmann graphs
- Hypercontractivity, sum-of-squares proofs, and their applications
- Some optimal inapproximability results
- Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
- Rounding Semidefinite Programming Hierarchies via Global Correlation
- Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for Graph Partitioning and Quadratic Integer Programming with PSD Objectives
- The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative-Type Metrics into ℓ 1
- Better Balance by Being Biased: A 0.8776-Approximation for Max Bisection
- Approximability and proof complexity
- Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
- Expander flows, geometric embeddings and graph partitioning
- On the complexity of \(k\)-SAT
- Complexity of Positivstellensatz proofs for the knapsack
This page was built for publication: Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut
