The cut cone,L1 embeddability, complexity, and multicommodity flows
From MaRDI portal
Publication:3984283
DOI10.1002/net.3230210602zbMath0748.90015OpenAlexW2059742977MaRDI QIDQ3984283
Publication date: 27 June 1992
Published in: Networks (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/net.3230210602
Abstract computational complexity for mathematical programming problems (90C60) Deterministic network models in operations research (90B10)
Related Items
Metric extensions and the \(L^ 1\) hierarchy, Application of cut polyhedra. I, Applications of cut polyhedra. II, On Flattenability of Graphs, New classes of facets of the cut polytope and tightness of \(I_{mm22}\) Bell inequalities, Finite metrics in switching classes, Graphic vertices of the metric polytope, \(L_ 1\)-embeddability of rectilinear polygons with holes, Approximation algorithms for feasible cut and multicut problems, Compression bounds for Lipschitz maps from the Heisenberg group to \(L_{1}\), Tail-dependence, exceedance sets, and metric embeddings, The complexity of LSH feasibility, Embedding into \(l_{\infty }^{2}\) is easy, embedding into \(l_{\infty}^{3}\) is NP-complete, Generating facets for the cut polytope of a graph by triangular elimination, A bounded compactness theorem for \(L^ 1\)-embeddability of metric spaces in the plane, Facets for the cut cone. I, Facets for the cut cone. II: Clique-web inequalities, Embedding into the rectilinear plane in optimal \(O(n^{2})\) time, The projected pairwise multicommodity flow polyhedron, A bound on the \(k\)-gonality of facets of the hypermetric cone and related complexity problems, Threshold Dynamics for Networks with Arbitrary Surface Tensions, Complexity of the Positive Semidefinite Matrix Completion Problem with a Rank Constraint, Hypercube embedding of generalized bipartite metrics, Fullerenes and coordination polyhedra versus half-cube embeddings, The hypermetric cone is polyhedral, Collapsing and lifting for the cut cone
Cites Work
- Isometric embedding in \(\ell_ p\)-spaces
- Sur les inégalités valides dans \(L^ 1\)
- Root system graphs
- Geometric algorithms and combinatorial optimization
- All the facets of the six-point Hamming cone
- All facets of the cut cone \(C_ n\) for \(n=7\) are known
- Hypermetric Spaces and the Hamming Cone
- On the Extreme Rays of the Metric Cone
