Smallest compact formulation for the permutahedron
From MaRDI portal
Publication:745678
DOI10.1007/s10107-014-0757-1zbMath1322.90048OpenAlexW2068066892MaRDI QIDQ745678
Publication date: 14 October 2015
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: http://hdl.handle.net/1721.1/87079
Related Items
The rectangle covering number of random Boolean matrices, Heuristics for exact nonnegative matrix factorization, Lifting for Simplicity: Concise Descriptions of Convex Sets, Extended formulations for sparsity matroids, Equivariant Semidefinite Lifts and Sum-of-Squares Hierarchies, Computational complexity of computing a quasi-proper equilibrium, Convex Relaxations for Permutation Problems, A Lower Bound on the Positive Semidefinite Rank of Convex Bodies, Polytopes of minimum positive semidefinite rank, The matching problem has no small symmetric SDP, Limitations of the hyperplane separation technique for bounding the extension complexity of polytopes, Minimum linear arrangements, Generalized permutahedra: Minkowski linear functionals and Ehrhart positivity, Lifts for Voronoi cells of lattices, Simple extensions of polytopes, Maximum semidefinite and linear extension complexity of families of polytopes, Some \(0/1\) polytopes need exponential size extended formulations, Nondeterministic Communication Complexity of Random Boolean Functions (Extended Abstract), Continuation methods for approximate large scale object sequencing, A geometric lower bound on the extension complexity of polytopes based on the \(f\)-vector, Constructing Extended Formulations from Reflection Relations, On the linear extension complexity of regular \(n\)-gons, Nonnegative rank factorization -- a heuristic approach via rank reduction, On the geometric interpretation of the nonnegative rank, Extended formulations for polygons, Unnamed Item, A Comprehensive Analysis of Polyhedral Lift-and-Project Methods, A short convex-hull proof for the all-different system with the inclusion property, Mixed Integer Linear Programming Formulation Techniques, Lower bounds on nonnegative rank via nonnegative nuclear norms, On the existence of 0/1 polytopes with high semidefinite extension complexity, On the linear extension complexity of stable set polytopes for perfect graphs, Solving LP Relaxations of Some NP-Hard Problems Is As Hard As Solving Any Linear Program, $L_p$-norm Regularization Algorithms for Optimization Over Permutation Matrices, Lower bounds on matrix factorization ranks via noncommutative polynomial optimization, Permutatorial optimization via the permutahedron, Tight Lower Bounds on the Sizes of Symmetric Extensions of Permutahedra and Similar Results, Convexification of Permutation-Invariant Sets and an Application to Sparse Principal Component Analysis
Cites Work
- Unnamed Item
- Improved sorting networks with O(log N) depth
- Sorting in \(c \log n\) parallel steps
- Expressing combinatorial optimization problems by linear programs
- Combinatorial bounds on nonnegative rank and extended formulations
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Some \(0/1\) polytopes need exponential size extended formulations
- Tight Lower Bounds on the Sizes of Symmetric Extensions of Permutahedra and Similar Results
- Linear vs. semidefinite extended formulations
- An Inequality
- Extended formulations in combinatorial optimization
