Extended formulations for polygons
From MaRDI portal
Publication:714985
DOI10.1007/s00454-012-9421-9zbMath1290.68122arXiv1107.0371OpenAlexW2095405086MaRDI QIDQ714985
Hans Raj Tiwary, Samuel Fiorini, Thomas Rothvoß
Publication date: 15 October 2012
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1107.0371
Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (29)
Extended formulations for convex heptagons ⋮ Heuristics for exact nonnegative matrix factorization ⋮ Common information and unique disjointness ⋮ Extension complexity of low-dimensional polytopes ⋮ Polytopes of minimum positive semidefinite rank ⋮ Limitations of the hyperplane separation technique for bounding the extension complexity of polytopes ⋮ On Ranks of Regular Polygons ⋮ Complexity of combinatorial optimization problems in terms of face lattices of associated polytopes ⋮ On the extension complexity of polytopes separating subsets of the Boolean cube ⋮ Combinatorial optimization. Abstracts from the workshop held November 7--13, 2021 (hybrid meeting) ⋮ Maximum semidefinite and linear extension complexity of families of polytopes ⋮ Some \(0/1\) polytopes need exponential size extended formulations ⋮ Euclidean distance matrices and separations in communication complexity theory ⋮ Extension complexity and realization spaces of hypersimplices ⋮ On the linear extension complexity of regular \(n\)-gons ⋮ Polygons as sections of higher-dimensional polytopes ⋮ An Almost Optimal Algorithm for Computing Nonnegative Rank ⋮ Extended formulations in combinatorial optimization ⋮ Polyhedral approximation of ellipsoidal uncertainty sets via extended formulations: a computational case study ⋮ Algorithms for positive semidefinite factorization ⋮ Realizability of polytopes as a low rank matrix completion problem ⋮ Tropical lower bounds for extended formulations ⋮ On the existence of 0/1 polytopes with high semidefinite extension complexity ⋮ Worst-case results for positive semidefinite rank ⋮ Computing a Nonnegative Matrix Factorization---Provably ⋮ Extension Complexity of Polytopes with Few Vertices or Facets ⋮ Tropical lower bound for extended formulations. II. Deficiency graphs of matrices ⋮ An upper bound for nonnegative rank ⋮ Small extended formulations for cyclic polytopes
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Nonnegative ranks, decompositions, and factorizations of nonnegative matrices
- Smallest compact formulation for the permutahedron
- Extended formulations, nonnegative factorizations, and randomized communication protocols
- Sorting in \(c \log n\) parallel steps
- Using separation algorithms to generate mixed integer model reformulations
- Expressing combinatorial optimization problems by linear programs
- Combinatorial bounds on nonnegative rank and extended formulations
- Some \(0/1\) polytopes need exponential size extended formulations
- Constructing Extended Formulations from Reflection Relations
- Reformulation and Decomposition of Integer Programs
- On Polyhedral Approximations of the Second-Order Cone
- Extended formulations in combinatorial optimization
This page was built for publication: Extended formulations for polygons
