Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut (Q5009512): Difference between revisions

Latest revision as of 10:01, 30 July 2024

scientific article; zbMATH DE number 7378632

Language	Label	Description	Also known as
English	Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut	scientific article; zbMATH DE number 7378632

Statements

instance of

scholarly article

0 references

DOI

10.4230/LIPIcs.APPROX-RANDOM.2018.20

0 references

0 references

0 references

4 August 2021

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

approximation algorithms

0 references

exponential-time algorithms

0 references

vertex cover

0 references

sparsest cut

0 references

balanced separator

0 references

MaRDI profile type

MaRDI publication profile

0 references

cites work

O(√log n) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems

0 references

Subexponential Algorithms for Unique Games and Related Problems

0 references

Euclidean distortion and the sparsest cut

0 references

Proof verification and the hardness of approximation problems

0 references

Expander flows, geometric embeddings and graph partitioning

0 references

Probabilistic checking of proofs

0 references

Better Balance by Being Biased: A 0.8776-Approximation for Max Bisection

0 references

Optimal Long Code Test with One Free Bit

0 references

Q3337223

0 references

Hypercontractivity, sum-of-squares proofs, and their applications

0 references

Rounding Semidefinite Programming Hierarchies via Global Correlation

0 references

Sum-of-squares proofs and the quest toward optimal algorithms

0 references

Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms

0 references

\(\ell ^2_2\) spreading metrics for vertex ordering problems

0 references

Local Global Tradeoffs in Metric Embeddings

0 references

On the hardness of approximating Multicut and Sparsest-Cut

0 references

Towards a proof of the 2-to-1 games conjecture?

0 references

On non-optimally expanding sets in Grassmann graphs

0 references

On the hardness of approximating minimum vertex cover

0 references

Relations between average case complexity and approximation complexity

0 references

Improved Approximation Algorithms for Minimum Weight Vertex Separators

0 references

An improved approximation ratio for the minimum linear arrangement problem

0 references

Q4198056

0 references

Complexity of Positivstellensatz proofs for the knapsack

0 references

Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for Graph Partitioning and Quadratic Integer Programming with PSD Objectives

0 references

Improved Approximation Algorithms for the Vertex Cover Problem in Graphs and Hypergraphs

0 references

Some optimal inapproximability results

0 references

On the complexity of \(k\)-SAT

0 references

Which problems have strongly exponential complexity?

0 references

A better approximation ratio for the vertex cover problem

0 references

On the power of unique 2-prover 1-round games

0 references

Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique

0 references

Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?

0 references

On independent sets, 2-to-2 games, and Grassmann graphs

0 references

Vertex cover might be hard to approximate to within \(2 - \varepsilon \)

0 references

The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative-Type Metrics into ℓ <sub>1</sub>

0 references

Sum of squares lower bounds for refuting any CSP

0 references

An Explicit Equivalent Positive Semidefinite Program for Nonlinear 0-1 Programs

0 references

Q2921657

0 references

Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms

0 references

Q5111409

0 references

Ramsey numbers and an approximation algorithm for the vertex cover problem

0 references

Two-query PCP with subconstant error

0 references

Q4496025

0 references

Approximability and proof complexity

0 references

Graph expansion and the unique games conjecture

0 references

Q5743406

0 references

Approximation schemes via Sherali-Adams hierarchy for dense constraint satisfaction problems and assignment problems

0 references

full work available at URL

https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2018.20

0 references

OpenAlex ID

W2888878694

0 references

title

Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut (English)

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:5009512

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