Enumeration of 2-level polytopes

DOI10.1007/s12532-018-0145-6zbMath1414.05023arXiv1703.01943OpenAlexW1678874697WikidataQ129282662 ScholiaQ129282662MaRDI QIDQ1741129

Adam Bohn, Marco Macchia, Samuel Fiorini, Vissarion Fisikopoulos, Yuri Faenza, Kanstantsin Pashkovich

Publication date: 3 May 2019

Published in: Mathematical Programming Computation, Algorithms - ESA 2015 (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1703.01943

zbMATH Keywords

optimizationformal concept analysispolyhedral computationpolyhedral combinatoricsalgorithm engineering

Mathematics Subject Classification ID

Semidefinite programming (90C22) Exact enumeration problems, generating functions (05A15) Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Computational aspects related to convexity (52B55) Nonnumerical algorithms (68W05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Perfect graphs (05C17)

Related Items

Bounds on the number of 2-level polytopes, cones, and configurations, Extended formulations for matroid polytopes through randomized protocols, Binary scalar products, Octopuses in the Boolean cube: families with pairwise small intersections. I, Complex psd-minimal polytopes in dimensions two and three, Enumeration of 2-level polytopes, Properties of combinatorial optimization problems over polyhedral-spherical sets, Four-dimensional polytopes of minimum positive semidefinite rank, Projectively unique polytopes and toric slack ideals, 2L_enum, On Vertices and Facets of Combinatorial 2-Level Polytopes, Two-Level Polytopes with a Prescribed Facet, An algebraic approach to projective uniqueness with an application to order polytopes

Uses Software

• nauty
• polymake
• Boost C++ Libraries
• CRAN
• Traces
• Boost
• uBLAS
• 01poly
• CPAN
• birkhoff faces
• 2L_enum

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Faces of Birkhoff Polytopes
• Polytopes of minimum positive semidefinite rank
• Theta rank, levelness, and matroid minors
• Four-dimensional polytopes of minimum positive semidefinite rank
• The number of faces of centrally-symmetric polytopes
• Compressed polytopes and statistical disclosure limitation
• Many 2-level polytopes from matroids
• Triangulations. Structures for algorithms and applications
• On Kalai's conjectures concerning centrally symmetric polytopes
• Two poset polytopes
• Finding all closed sets: A general approach
• Expressing combinatorial optimization problems by linear programs
• Geometric algorithms and combinatorial optimization.
• On determining the congruence of point sets in \(d\) dimensions
• On certain polytopes associated with graphs
• Enumeration of 2-level polytopes
• On the geometric interpretation of the nonnegative rank
• Computing the face lattice of a polytope from its vertex-facet incidences
• The lattices of closure systems, closure operators, and implicational systems on a finite set: A survey
• Complete enumeration of small realizable oriented matroids
• Algorithms for tight spans and tropical linear spaces
• Which nonnegative matrices are slack matrices?
• Practical graph isomorphism. II.
• Combinatorial Optimization
• On Vertices and Facets of Combinatorial 2-Level Polytopes
• Two-Level Polytopes with a Prescribed Facet
• Nonnegative polynomials and sums of squares
• Theta Bodies for Polynomial Ideals
• Intersections of translates of convex bodies
• On a certain class of polytopes associated with independence systems.
• Decompositions of Rational Convex Polytopes
• Lectures on Polytopes
• Comparing performance of algorithms for generating concept lattices
• Polymake: an approach to modular software design in computational geometry