The cut polyhedra are shown to be exceptional among other polyhedra, by the great diversity of their applications. In this first part of their paper, the authors show that these may include \(\ell_1\)-metrics and other similar objects arising from graphs, normed spaces and lattices.
Recommendations
Cites work
- \(\ell_ 1\)-rigid graphs
- 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
- A Review of Hierarchical Classification
- 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 ``average distance inequality for large subsets of the cube
- An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
- 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
- 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?)
- Hypercube embedding of generalized bipartite metrics
- HYPERMETRIC GRAPHS
- 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 completely monontone functions
- Metric Spaces and Positive Definite Functions
- On a facet of the balanced subgraph polytope
- On cuts and matchings in planar graphs
- On Isometric Embeddings of Graphs
- On scale embeddings of graphs into hypercubes
- On the Addressing Problem for Loop Switching
- On the cut polytope
- On the cycle polytope of a binary matroid
- On the Extreme Rays of the Metric Cone
- 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 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 CW-inequalities for vectors in \(\ell_ 1\)
- 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
Cited in
(18)- Combinatorial 5/6-approximation of Max Cut in graphs of maximum degree 3
- Solving quadratic (0,1)-problems by semidefinite programs and cutting planes
- Algebraic and numerical techniques for the computation of matrix determinants
- Applications of cut polyhedra. II
- Seminormality, canonical modules, and regularity of cut polytopes
- Learning representations from dendrograms
- New classes of facets of the cut polytope and tightness of \(I_{mm22}\) Bell inequalities
- Generating facets for the cut polytope of a graph by triangular elimination
- Monotone maps, sphericity and bounded second eigenvalue
- A dynamic inequality generation scheme for polynomial programming
- Improved compact formulations for metric and cut polyhedra
- Generating cutting planes for the semidefinite relaxation of quadratic programs
- Mathematical programming models and exact algorithms
- Maximum cut parameterized by crossing number
- Classes of cut ideals and their Betti numbers
- Cycle algebras and polytopes of matroids
- Branch-and-bound algorithms for the K -cluster problem based on SDP bounds evaluated by Lagrangian relaxation
- On random classical marginal problems with applications to quantum information theory
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)
