Convex Relaxations and Integrality Gaps (Q2802523)

From MaRDI portal

Jump to:navigation, search

scientific article

Language	Label	Description	Also known as
English	Convex Relaxations and Integrality Gaps	scientific article

Statements

scholarly article

0 references

Convex Relaxations and Integrality Gaps (English)

0 references

Eden Chlamtáč

0 references

Madhur Tulsiani

0 references

International Series in Operations Research & Management Science

0 references

publication date

26 April 2016

0 references

MaRDI profile type

MaRDI publication profile

0 references

full work available at URL

https://doi.org/10.1007/978-1-4614-0769-0_6

0 references

Towards strong nonapproximability results in the Lovasz-Schrijver hierarchy

0 references

Approximating the independence number via the \(\vartheta\)-function

0 references

Euclidean distortion and the sparsest cut

0 references

0 references

New approximation guarantee for chromatic number

0 references

MaxMin allocation via degree lower-bounded arborescences

0 references

Short proofs are narrow—resolution made simple

0 references

An \(\tilde{O}(n^{3/14})\)-coloring algorithm for 3-colorable graphs

0 references

New approximation algorithms for graph coloring

0 references

0 references

0 references

0 references

Integrality gaps for Sherali-Adams relaxations

0 references

A $(\log n)^{\Omega(1)}$ Integrality Gap for the Sparsest Cut SDP

0 references

Improved Approximation Guarantees through Higher Levels of SDP Hierarchies

0 references

Edmonds polytopes and a hierarchy of combinatorial problems

0 references

0 references

Integrality gaps for sparsest cut and minimum linear arrangement problems

0 references

Zero knowledge and the chromatic number

0 references

Forbidden Intersections

0 references

Integrality Gaps of $2-o(1)$ for Vertex Cover SDPs in the Lovász–Schrijver Hierarchy

0 references

Optimal Sherali-Adams Gaps from Pairwise Independence

0 references

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

0 references

The Operator $\Psi$ for the Chromatic Number of a Graph

0 references

Coloring -colorable graphs using relatively small palettes

0 references

Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems

0 references

Approximate graph coloring by semidefinite programming

0 references

Integrality Gaps of Linear and Semi-Definite Programming Relaxations for Knapsack

0 references

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

0 references

SDP Integrality Gaps with Local ell_1-Embeddability

0 references

The Lovász Theta Function and a Semidefinite Programming Relaxation of Vertex Cover

0 references

Improved Lower Bounds for Embeddings into $L_1$

0 references

0 references

0 references

A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming

0 references

Fast Approximation Algorithms for Knapsack Problems

0 references

0 references

On the Shannon capacity of a graph

0 references

Cones of Matrices and Set-Functions and 0–1 Optimization

0 references

Robust Algorithms for on Minor-Free Graphs Based on the Sherali-Adams Hierarchy

0 references

0 references

Integrality Gaps for Strong SDP Relaxations of UNIQUE GAMES

0 references

0 references

A comparison of the Delsarte and Lovász bounds

0 references

A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems

0 references

Max cut and the smallest eigenvalue

0 references

CSP gaps and reductions in the lasserre hierarchy

0 references

0 references

Identifiers

zbMATH Open document ID

0 references

10.1007/978-1-4614-0769-0_6

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

zbMATH DE Number

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:2802523

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