Strong reductions for extended formulations (Q1801022): Difference between revisions

← Older edit

@@ aliases / en / 0 / aliases / en / 0 @@
+Strong Reductions for Extended Formulations
@@ description / en / description / en @@
-scientific article
+scientific article; zbMATH DE number 6610502
@@ Property / title @@
+Strong Reductions for Extended Formulations (English)
@@ Property / title: Strong Reductions for Extended Formulations (English) / rank @@
+Normal rank
@@ Property / zbMATH Open document ID @@
+.90062
@@ Property / zbMATH Open document ID: 1419.90062 / rank @@
+Normal rank
@@ Property / DOI @@
+.1007/978-3-319-33461-5_29
@@ Property / DOI: 10.1007/978-3-319-33461-5_29 / rank @@
+Normal rank
@@ Property / published in @@
+Integer Programming and Combinatorial Optimization
+Normal rank
@@ Property / publication date @@
+August 2016Timestamp +2016-08-10T00:00:00Z
Timezone +00:00
Calendar Gregorian
Precision 1 day
Before 0
After 0
-Timestamp
++2016-08-10T00:00:00Z
-Timezone
++00:00
-Calendar
+Gregorian
-Precision
+day
 Before
 After
@@ Property / publication date: 10 August 2016 / rank @@
+Normal rank
@@ Property / Mathematics Subject Classification ID @@
+C22
@@ Property / Mathematics Subject Classification ID: 90C22 / rank @@
+Normal rank
@@ Property / Mathematics Subject Classification ID @@
+C32
@@ Property / Mathematics Subject Classification ID: 90C32 / rank @@
+Normal rank
@@ Property / zbMATH DE Number @@
+6610502
@@ Property / zbMATH DE Number: 6610502 / rank @@
+Normal rank
@@ Property / OpenAlex ID @@
+W2219311948
@@ Property / OpenAlex ID: W2219311948 / rank @@
+Normal rank
@@ Property / arXiv ID @@
+.04932
@@ Property / arXiv ID: 1512.04932 / rank @@
+Normal rank
@@ Property / cites work @@
+Inapproximability of Combinatorial Problems via Small LPs and SDPs
+Normal rank
@@ Property / cites work @@
+Expressing combinatorial optimization problems by linear programs
+Normal rank
@@ Property / cites work @@
+The Matching Polytope has Exponential Extension Complexity
+Normal rank
@@ Property / cites work @@
+Linear vs. semidefinite extended formulations
@@ Property / cites work: Linear vs. semidefinite extended formulations / rank @@
+Normal rank
@@ Property / cites work @@
+Lower Bounds on the Size of Semidefinite Programming Relaxations
+Normal rank
@@ Property / cites work @@
+Approximation Limits of Linear Programs (Beyond Hierarchies)
+Normal rank
@@ Property / cites work @@
+Approximate Constraint Satisfaction Requires Large LP Relaxations
+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 @@
+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 @@
+The stable set problem and the lift-and-project ranks of graphs
+Normal rank
@@ Property / cites work @@
+On a Representation of the Matching Polytope Via Semidefinite Liftings
+Normal rank
@@ Property / cites work @@
+Extension Complexity, MSO Logic, and Treewidth
@@ Property / cites work: Extension Complexity, MSO Logic, and Treewidth / rank @@
+Normal rank
@@ Property / cites work @@
+Sparsest cut on bounded treewidth graphs
@@ Property / cites work: Sparsest cut on bounded treewidth graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Euclidean distortion and the sparsest cut
@@ Property / cites work: Euclidean distortion and the sparsest cut / rank @@
+Normal rank
@@ Property / cites work @@
+A $(\log n)^{\Omega(1)}$ Integrality Gap for the Sparsest Cut SDP
+Normal rank
@@ Property / cites work @@
+On the hardness of approximating Multicut and Sparsest-Cut
+Normal rank
@@ Property / cites work @@
+Gadgets, Approximation, and Linear Programming
@@ Property / cites work: Gadgets, Approximation, and Linear Programming / rank @@
+Normal rank
@@ Property / cites work @@
+Complexity Analyses of Bienstock–Zuckerberg and Lasserre Relaxations on the Matching and Stable Set Polytopes
+Normal rank
@@ Property / cites work @@
+Optimal Long Code Test with One Free Bit
@@ Property / cites work: Optimal Long Code Test with One Free Bit / rank @@
+Normal rank
@@ Property / cites work @@
+The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative-Type Metrics into ℓ             <sub>1</sub>
+Normal rank
@@ Property / cites work @@
+Approximating rectangles by juntas and weakly-exponential lower bounds for LP relaxations of CSPs
+Normal rank