The hypermetric cone is polyhedral

DOI10.1007/BF01303512zbMath0801.52009MaRDI QIDQ1316645

Viatcheslav Grishukhin, Michel Marie Deza, Monique Laurent

Publication date: 1 December 1994

Published in: Combinatorica (Search for Journal in Brave)

zbMATH Keywords

quadratic formspolyhedral conelattice polytopeshypermetric

Mathematics Subject Classification ID

Lattices and convex bodies in (n) dimensions (aspects of discrete geometry) (52C07) Lattice polytopes in convex geometry (including relations with commutative algebra and algebraic geometry) (52B20) Lattices and convex bodies (number-theoretic aspects) (11H06) Convex sets in (n) dimensions (including convex hypersurfaces) (52A20)

Related Items

The Boolean Quadric Polytope, Application of cut polyhedra. I, Applications of cut polyhedra. II, Lattice-free polytopes and their diameter, Small Cones of Oriented Semi-Metrics, Delaunay transformations of a Delaunay polytope, Finite metric spaces of strictly negative type, On a class of metrics related to graph layout problems, Binary Positive Semidefinite Matrices and Associated Integer Polytopes, A Hierarchy of Subgraph Projection-Based Semidefinite Relaxations for Some NP-Hard Graph Optimization Problems, Complexity results for the gap inequalities for the max-cut problem, Binary positive semidefinite matrices and associated integer polytopes, The Hypermetric Cone on Seven Vertices, Facets for the cut cone. I, Facets for the cut cone. II: Clique-web inequalities, Semidefinite programming and combinatorial optimization, Membership testing for Bernoulli and tail-dependence matrices, Semidefinite relaxations for partitioning, assignment and ordering problems, Semidefinite relaxations for partitioning, assignment and ordering problems, A bound on the \(k\)-gonality of facets of the hypermetric cone and related complexity problems, The six-dimensional Delaunay polytopes, Solving quadratic (0,1)-problems by semidefinite programs and cutting planes

Cites Work

• Unnamed Item
• Sur les inégalités valides dans \(L^ 1\)
• The classification of finite connected hypermetric spaces
• Computing extreme rays of the metric cone for seven points
• Facets for the cut cone. I
• Facets for the cut cone. II: Clique-web inequalities
• All the facets of the six-point Hamming cone
• Über zwei Probleme bezüglich konvexer Körper von P. Erdős und von V.L. Klee
• The Empty Sphere
• Espaces Métriques Plongeables Dans Un Hypercube: Aspects Combinatoires
• On the Extreme Rays of the Metric Cone
• The cut cone,L1 embeddability, complexity, and multicommodity flows