Improved Approximation Guarantees through Higher Levels of SDP Hierarchies (Q3541786): Difference between revisions

@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1007/978-3-540-85363-3_5
+Normal rank
@@ Property / OpenAlex ID @@
+W1593162480
@@ Property / OpenAlex ID: W1593162480 / rank @@
+Normal rank
@@ Property / cites work @@
+Towards strong nonapproximability results in the Lovasz-Schrijver hierarchy
+Normal rank
@@ Property / cites work @@
+Q3002764
@@ Property / cites work: Q3002764 / rank @@
+Normal rank
@@ Property / cites work @@
+New approximation guarantee for chromatic number
@@ Property / cites work: New approximation guarantee for chromatic number / rank @@
+Normal rank
@@ Property / cites work @@
+Expander flows, geometric embeddings and graph partitioning
+Normal rank
@@ Property / cites work @@
+Integrality gaps for Sherali-Adams relaxations
@@ Property / cites work: Integrality gaps for Sherali-Adams relaxations / rank @@
+Normal rank
@@ Property / cites work @@
+Near-optimal algorithms for unique games
@@ Property / cites work: Near-optimal algorithms for unique games / rank @@
+Normal rank
@@ Property / cites work @@
+A PTAS for the minimization of polynomials of fixed degree over the simplex
+Normal rank
@@ Property / cites work @@
+The Probable Value of the Lovász--Schrijver Relaxations for Maximum Independent Set
+Normal rank
@@ Property / cites work @@
+Q5538132
@@ Property / cites work: Q5538132 / rank @@
+Normal rank
@@ Property / cites work @@
+Integrality Gaps of $2-o(1)$ for Vertex Cover SDPs in the Lovász–Schrijver Hierarchy
+Normal rank
@@ Property / cites work @@
+Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
+Normal rank
@@ Property / cites work @@
+Some optimal inapproximability results
@@ Property / cites work: Some optimal inapproximability results / rank @@
+Normal rank
@@ Property / cites work @@
+Coloring -colorable graphs using relatively small palettes
+Normal rank
@@ Property / cites work @@
+Approximate graph coloring by semidefinite programming
+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 @@
+Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
+Normal rank
@@ Property / cites work @@
+Approximating Coloring and Maximum Independent Sets in 3-Uniform Hypergraphs
+Normal rank
@@ Property / cites work @@
+A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
+Normal rank
@@ Property / cites work @@
+Q4537750
@@ Property / cites work: Q4537750 / rank @@
+Normal rank
@@ Property / cites work @@
+Cones of Matrices and Set-Functions and 0–1 Optimization
+Normal rank
@@ Property / cites work @@
+On the complexity of Putinar's Positivstellensatz
@@ Property / cites work: On the complexity of Putinar's Positivstellensatz / rank @@
+Normal rank
@@ Property / cites work @@
+Q3549708
@@ Property / cites work: Q3549708 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3549626
@@ Property / cites work: Q3549626 / rank @@
+Normal rank
@@ Property / cites work @@
+A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
+Normal rank
@@ Property / cites work @@
+Q2934582
@@ Property / cites work: Q2934582 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4828974
@@ Property / cites work: Q4828974 / rank @@
+Normal rank
@@ links / mardi / name / links / mardi / name @@
+Publication:3541786