Smallest compact formulation for the permutahedron
From MaRDI portal
Publication:745678
DOI10.1007/s10107-014-0757-1zbMath1322.90048MaRDI 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
90C10: Integer programming
Related Items
A Lower Bound on the Positive Semidefinite Rank of Convex Bodies, Unnamed Item, Lifting for Simplicity: Concise Descriptions of Convex Sets, Solving LP Relaxations of Some NP-Hard Problems Is As Hard As Solving Any Linear Program, 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, Generalized permutahedra: Minkowski linear functionals and Ehrhart positivity, Lifts for Voronoi cells of lattices, Heuristics for exact nonnegative matrix factorization, Extended formulations for sparsity matroids, Polytopes of minimum positive semidefinite rank, On the linear extension complexity of regular \(n\)-gons, Continuation methods for approximate large scale object sequencing, Extended formulations for polygons, Lower bounds on nonnegative rank via nonnegative nuclear norms, On the existence of 0/1 polytopes with high semidefinite extension complexity, Simple extensions of polytopes, The matching problem has no small symmetric SDP, Maximum semidefinite and linear extension complexity of families of polytopes, On the geometric interpretation of the nonnegative rank, A short convex-hull proof for the all-different system with the inclusion property, A geometric lower bound on the extension complexity of polytopes based on the \(f\)-vector, Permutatorial optimization via the permutahedron, Computational complexity of computing a quasi-proper equilibrium, Nonnegative rank factorization -- a heuristic approach via rank reduction, On the linear extension complexity of stable set polytopes for perfect graphs, Lower bounds on matrix factorization ranks via noncommutative polynomial optimization, The rectangle covering number of random Boolean matrices, Minimum linear arrangements, Some \(0/1\) polytopes need exponential size extended formulations, Limitations of the hyperplane separation technique for bounding the extension complexity of polytopes, A Comprehensive Analysis of Polyhedral Lift-and-Project Methods, Mixed Integer Linear Programming Formulation Techniques, $L_p$-norm Regularization Algorithms for Optimization Over Permutation Matrices, Nondeterministic Communication Complexity of Random Boolean Functions (Extended Abstract), Constructing Extended Formulations from Reflection Relations, Equivariant Semidefinite Lifts and Sum-of-Squares Hierarchies, Convex Relaxations for Permutation Problems
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
