An unbounded sum-of-squares hierarchy integrality gap for a polynomially solvable problem (Q1683679): Difference between revisions

@@ Property / DOI @@
-.1007/s10107-016-1102-7
@@ Property / DOI: 10.1007/s10107-016-1102-7 / rank @@
-Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1007/s10107-016-1102-7
+Normal rank
@@ Property / OpenAlex ID @@
+W2570315187
@@ Property / OpenAlex ID: W2570315187 / rank @@
+Normal rank
@@ Property / cites work @@
+The Geometry of Scheduling
@@ Property / cites work: The Geometry of Scheduling / rank @@
+Normal rank
@@ Property / cites work @@
+Sum of Squares Lower Bounds from Pairwise Independence
+Normal rank
@@ Property / cites work @@
+Q5743407
@@ Property / cites work: Q5743407 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4952606
@@ Property / cites work: Q4952606 / rank @@
+Normal rank
@@ Property / cites work @@
+Computation of the Lasserre Ranks of Some Polytopes
+Normal rank
@@ Property / cites work @@
+A Primal-Dual Approximation Algorithm for Min-Sum Single-Machine Scheduling Problems
+Normal rank
@@ Property / cites work @@
+Convex Relaxations and Integrality Gaps
@@ Property / cites work: Convex Relaxations and Integrality Gaps / rank @@
+Normal rank
@@ Property / cites work @@
+Complexity of Positivstellensatz proofs for the knapsack
+Normal rank
@@ Property / cites work @@
+Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity
+Normal rank
@@ Property / cites work @@
+Integrality Gaps of Linear and Semi-Definite Programming Relaxations for Knapsack
+Normal rank
@@ Property / cites work @@
+Reducibility among Combinatorial Problems
@@ Property / cites work: Reducibility among Combinatorial Problems / rank @@
+Normal rank
@@ Property / cites work @@
+Tight Sum-Of-Squares Lower Bounds for Binary Polynomial Optimization Problems.
+Normal rank
@@ Property / cites work @@
+On the Hardest Problem Formulations for the $$0/1$$ Lasserre Hierarchy
+Normal rank
@@ Property / cites work @@
+Sum-of-squares hierarchy lower bounds for symmetric formulations
+Normal rank
@@ Property / cites work @@
+Global Optimization with Polynomials and the Problem of Moments
+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 @@
+Lower Bound for the Number of Iterations in Semidefinite Hierarchies for the Cut Polytope
+Normal rank
@@ Property / cites work @@
+Sum-of-squares Lower Bounds for Planted Clique
@@ Property / cites work: Sum-of-squares Lower Bounds for Planted Clique / rank @@
+Normal rank
@@ Property / cites work @@
+A Primal-Dual Approximation Algorithm for Min-Sum Single-Machine Scheduling Problems
+Normal rank
@@ Property / cites work @@
+An <i>n</i> Job, One Machine Sequencing Algorithm for Minimizing the Number of Late Jobs
+Normal rank
@@ Property / cites work @@
+Approximability and proof complexity
@@ Property / cites work: Approximability and proof complexity / rank @@
+Normal rank
@@ Property / cites work @@
+Exact Semidefinite Programming Relaxations with Truncated Moment Matrix for Binary Polynomial Optimization Problems
+Normal rank
@@ Property / cites work @@
+Class of global minimum bounds of polynomial functions
+Normal rank
@@ Property / cites work @@
+CSP gaps and reductions in the lasserre hierarchy
@@ Property / cites work: CSP gaps and reductions in the lasserre hierarchy / rank @@
+Normal rank
@@ Property / cites work @@
+Faces for a linear inequality in 0–1 variables
@@ Property / cites work: Faces for a linear inequality in 0–1 variables / rank @@
+Normal rank
@@ Property / DOI @@
+.1007/S10107-016-1102-7
@@ Property / DOI: 10.1007/S10107-016-1102-7 / rank @@
+Normal rank