No label defined (Q5009512)

From MaRDI portal

Revision as of 07:47, 26 July 2024 by ReferenceBot (talk | contribs) (‎Changed an Item)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Jump to:navigation, search

scientific article; zbMATH DE number 7378632

Language	Label	Description	Also known as
English	No label defined	scientific article; zbMATH DE number 7378632

Statements

scholarly article

0 references

Pasin Manurangsi

0 references

0 references

publication date

4 August 2021

0 references

zbMATH Keywords

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

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

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

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

0 references

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

0 references

0 references

Ramsey numbers and an approximation algorithm for the vertex cover problem

0 references

Two-query PCP with subconstant error

0 references

0 references

Approximability and proof complexity

0 references

Graph expansion and the unique games conjecture

0 references

0 references

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

0 references

Identifiers

10.4230/LIPIcs.APPROX-RANDOM.2018.20

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

zbMATH DE Number

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:5009512

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Item:Q5009512&oldid=36704079"