New limits of treewidth-based tractability in optimization
From MaRDI portal
Publication:2118087
DOI10.1007/s10107-020-01563-5zbMath1489.90204arXiv1807.02551OpenAlexW3085455169MaRDI QIDQ2118087
Sebastian Pokutta, Gonzalo Muñoz, Yuri Faenza
Publication date: 22 March 2022
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1807.02551
Programming involving graphs or networks (90C35) Semidefinite programming (90C22) Linear programming (90C05)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Average case polyhedral complexity of the maximum stable set problem
- On the extension complexity of combinatorial polytopes
- On the existence of 0/1 polytopes with high semidefinite extension complexity
- Positive semidefinite rank
- Graph minors. III. Planar tree-width
- Extended formulation for CSP that is compact for instances of bounded treewidth
- Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
- Tree clustering for constraint networks
- Expressing combinatorial optimization problems by linear programs
- S-functions for graphs
- Quickly excluding a planar graph
- Strong reductions for extended formulations
- Extension complexity of the correlation polytope
- A generalization of extension complexity that captures P
- Tree-width and the Sherali-Adams operator
- Incidence matrices and interval graphs
- Extension complexities of Cartesian products involving a pyramid
- Parameterized extension complexity of independent set and related problems
- Some \(0/1\) polytopes need exponential size extended formulations
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Exponential Lower Bounds for Polytopes in Combinatorial Optimization
- Graph Theory
- On the Existence of 0/1 Polytopes with High Semidefinite Extension Complexity
- Lower Bounds on the Size of Semidefinite Programming Relaxations
- Polynomial Bounds for the Grid-Minor Theorem
- Easy problems for tree-decomposable graphs
- Approximation Limits of Linear Programs (Beyond Hierarchies)
- The complexity of homomorphism and constraint satisfaction problems seen from the other side
- Graphical Models, Exponential Families, and Variational Inference
- Graph minors. II. Algorithmic aspects of tree-width
- Complexity of Finding Embeddings in a k-Tree
- A sufficient condition for backtrack-bounded search
- Polynomial-time self-reducibility: theoretical motivations and practical results∗
- APPROXIMATING POLYGONS AND SUBDIVISIONS WITH MINIMUM-LINK PATHS
- Extension Complexity of Independent Set Polytopes
- LP Formulations for Polynomial Optimization Problems
- The Matching Polytope has Exponential Extension Complexity
- Linear-time computation of optimal subgraphs of decomposable graphs
- Demand Queries with Preprocessing
- Lifts of Convex Sets and Cone Factorizations
- A Note on Treewidth in Random Graphs
- No Small Linear Program Approximates Vertex Cover Within a Factor 2 − ɛ
- Computational Complexity
- Extension Complexity, MSO Logic, and Treewidth
- Linear vs. semidefinite extended formulations
- On Integer Programming and the Branch-Width of the Constraint Matrix
- Some optimal inapproximability results
- Sums of Squares and Semidefinite Program Relaxations for Polynomial Optimization Problems with Structured Sparsity
- Convergent SDP‐Relaxations in Polynomial Optimization with Sparsity
This page was built for publication: New limits of treewidth-based tractability in optimization
