Application of cut polyhedra. I

DOI10.1016/0377-0427(94)90020-5zbMath0826.52012OpenAlexW1986175898MaRDI QIDQ1891019

Monique Laurent, Michel Marie Deza

Publication date: 28 May 1995

Published in: Journal of Computational and Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0377-0427(94)90020-5

zbMATH Keywords

cut polyhedrahypermetric\(\ell_ 1\)-metricgraphic metric

Mathematics Subject Classification ID

Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Gale and other diagrams (52B35)

Related Items

Mathematical Programming Models and Exact Algorithms, Applications of cut polyhedra. II, New classes of facets of the cut polytope and tightness of \(I_{mm22}\) Bell inequalities, Improved compact formulations for metric and cut polyhedra, Generating cutting planes for the semidefinite relaxation of quadratic programs, Algebraic and numerical techniques for the computation of matrix determinants, Classes of cut ideals and their Betti numbers, Cycle algebras and polytopes of matroids, Maximum Cut Parameterized by Crossing Number, Learning representations from dendrograms, Seminormality, canonical modules, and regularity of cut polytopes, Generating facets for the cut polytope of a graph by triangular elimination, Combinatorial 5/6-approximation of Max Cut in graphs of maximum degree 3, Solving quadratic (0,1)-problems by semidefinite programs and cutting planes, Monotone maps, sphericity and bounded second eigenvalue, A dynamic inequality generation scheme for polynomial programming

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The max-cut problem on graphs not contractible to \(K_ 5\)
• Antipodal graphs and oriented matroids
• The inequicut cone
• The even and odd cut polytopes
• On cuts and matchings in planar graphs
• An ``average distance inequality for large subsets of the cube
• Sur les inégalités valides dans \(L^ 1\)
• Lifting facets of the cut polytope
• On the cycle polytope of a binary matroid
• Combinatorial approaches to multiflow problems
• The classification of finite connected hypermetric spaces
• Collapse of the metric hierarchy for bipartite graphs
• Zonoid theory and Hilbert's fourth problem
• The Boolean quadratic polytope: Some characteristics, facets and relatives
• Correlation polytopes: Their geometry and complexity
• Computing extreme rays of the metric cone for seven points
• Extension operations for cuts
• Facets for the cut cone. I
• Facets for the cut cone. II: Clique-web inequalities
• Max-cut in circulant graphs
• On scale embeddings of graphs into hypercubes
• All the facets of the six-point Hamming cone
• The hypermetric cone is polyhedral
• \(\ell_ 1\)-rigid graphs
• Collapsing and lifting for the cut cone
• A bound on the \(k\)-gonality of facets of the hypermetric cone and related complexity problems
• The CW-inequalities for vectors in \(\ell_ 1\)
• All facets of the cut cone \(C_ n\) for \(n=7\) are known
• The cut polytope and the Boolean quadric polytope
• L-polytopes and equiangular lines
• Hypercube embedding of generalized bipartite metrics
• Applications of cut polyhedra. II
• Some new classes of facets for the equicut polytope
• Graphic vertices of the metric polytope
• The relation between hierarchical and Euclidean models for psychological distances
• A generalized cut-condition for multiflows in matroids
• Distance-preserving subgraphs of hypercubes
• The cone of distance matrices
• The equipartition polytope. I: Formulations, dimension and basic facets
• The equipartition polytope. II: Valid inequalities and facets
• Metric spaces and completely monontone functions
• A counterexample to Borsuk’s conjecture
• On Isometric Embeddings of Graphs
• Embeddings of Ultrametric Spaces in Finite Dimensional Structures
• On a facet of the balanced subgraph polytope
• An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
• The structure of distances in networks
• Hypermetric Spaces and the Hamming Cone
• Espaces Métriques Plongeables Dans Un Hypercube: Aspects Combinatoires
• On the Extreme Rays of the Metric Cone
• Extremal Metrics Induced by Graphs
• The cut cone,L1 embeddability, complexity, and multicommodity flows
• Clique-Web Facets for Multicut Polytopes
• Recognition of Tree Metrics
• HYPERMETRIC GRAPHS
• Cut-Polytopes, Boolean Quadric Polytopes and Nonnegative Quadratic Pseudo-Boolean Functions
• A Review of Hierarchical Classification
• On the cut polytope
• Some Network Flow Problems Solved with Pseudo-Boolean Programming
• Characterizations of derived graphs
• On the Addressing Problem for Loop Switching
• Addresses for graphs
• Metric Spaces and Positive Definite Functions
• The cut cone. III: On the role of triangle facets