Towards strong nonapproximability results in the Lovász-Schrijver hierarchy (Q430828): Difference between revisions

@@ Property / Mathematics Subject Classification ID @@
+Q17
@@ Property / Mathematics Subject Classification ID: 68Q17 / rank @@
+Normal rank
@@ Property / Mathematics Subject Classification ID @@
+W25
@@ Property / Mathematics Subject Classification ID: 68W25 / rank @@
+Normal rank
@@ Property / Mathematics Subject Classification ID @@
+C22
@@ Property / Mathematics Subject Classification ID: 90C22 / rank @@
+Normal rank
@@ Property / zbMATH DE Number @@
+6050356
@@ Property / zbMATH DE Number: 6050356 / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+NP-complete problems
@@ Property / zbMATH Keywords: NP-complete problems / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+approximation algorithm
@@ Property / zbMATH Keywords: approximation algorithm / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+proof complexity
@@ Property / zbMATH Keywords: proof complexity / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+lift and project methods
@@ Property / zbMATH Keywords: lift and project methods / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+matrix cut operators
@@ Property / zbMATH Keywords: matrix cut operators / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+lower bounds
@@ Property / zbMATH Keywords: lower bounds / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+random instances of 3SAT
@@ Property / zbMATH Keywords: random instances of 3SAT / rank @@
+Normal rank
@@ 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/s00037-011-0027-z
+Normal rank
@@ Property / OpenAlex ID @@
+W2007239493
@@ Property / OpenAlex ID: W2007239493 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3002764
@@ Property / cites work: Q3002764 / rank @@
+Normal rank
@@ Property / cites work @@
+Expander flows, geometric embeddings and graph partitioning
+Normal rank
@@ Property / cites work @@
+Q3002766
@@ Property / cites work: Q3002766 / rank @@
+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 @@
+A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover
+Normal rank
@@ Property / cites work @@
+On the hardness of approximating minimum vertex cover
+Normal rank
@@ Property / cites work @@
+A threshold of ln             <i>n</i>             for approximating set cover
+Normal rank
@@ Property / cites work @@
+Interactive proofs and the hardness of approximating cliques
+Normal rank
@@ Property / cites work @@
+The Probable Value of the Lovász--Schrijver Relaxations for Maximum Independent Set
+Normal rank
@@ Property / cites work @@
+Q3002778
@@ Property / cites work: Q3002778 / rank @@
+Normal rank
@@ Property / cites work @@
+When Does the Positive Semidefiniteness Constraint Help in Lifting Procedures?
+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 @@
+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 @@
+Cones of Matrices and Set-Functions and 0–1 Optimization
+Normal rank
@@ Property / cites work @@
+Integrality Gaps for Strong SDP Relaxations of UNIQUE GAMES
+Normal rank
@@ Property / cites work @@
+Q4527015
@@ Property / cites work: Q4527015 / 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 @@
+Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
+Normal rank
@@ Property / cites work @@
+Q2934582
@@ Property / cites work: Q2934582 / rank @@
+Normal rank
@@ links / mardi / name / links / mardi / name @@
+Publication:430828