Application of cut polyhedra. I

DOI10.1016/0377-0427(94)90020-5MaRDI QIDQ1891019zbMATH OpenOpenAlexFDO

Authors Monique Laurent, Michel 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

hypermetric\(\ell_ 1\)-metriccut polyhedragraphic metric

Mathematics Subject Classification ID

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

Recommendations

• Applications of cut polyhedra. II
• scientific article; zbMATH DE number 718853
• Geometry of cuts and metrics
• On the cut polytope
• Computations of metric/cut polyhedra and their relatives

Cites work

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

Cited in

(16)

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

This page was built for publication: Application of cut polyhedra. I

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1891019)