Geometry of cuts and metrics

DOI10.1007/978-3-642-04295-9zbMath1210.52001OpenAlexW2158907148WikidataQ56553472 ScholiaQ56553472MaRDI QIDQ5902168

Monique Laurent, Michel Marie Deza

Publication date: 28 October 2009

Published in: Algorithms and Combinatorics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-04295-9

zbMATH Keywords

hypermetrics\(l_1\) metricscut conecut polyhedraDelaunay polyhyper in latticeshypercube embeddable metricsmetric structure at groups

Mathematics Subject Classification ID

Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Lattices and convex bodies in (n) dimensions (aspects of discrete geometry) (52C07) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorics in computer science (68R05) Other designs, configurations (05B30) Distance in graphs (05C12) Research exposition (monographs, survey articles) pertaining to convex and discrete geometry (52-02)

Related Items (63)

On the diameter of lattice polytopes ⋮ Convex excess in partial cubes ⋮ Similarity-reduced diversities: the effective entropy and the reduced entropy ⋮ Distance geometry in quasihypermetric spaces. III ⋮ On the optimality of the random hyperplane rounding technique for MAX CUT ⋮ The Boolean Quadric Polytope ⋮ Vertical perimeter versus horizontal perimeter ⋮ Pythagorean powers of hypercubes ⋮ Characterizing subgraphs of Hamming graphs ⋮ Order distances and split systems ⋮ Computational study of valid inequalities for the maximum \(k\)-cut problem ⋮ Simple odd \(\beta \)-cycle inequalities for binary polynomial optimization ⋮ Generalized cut and metric polytopes of graphs and simplicial complexes ⋮ Bounds on the number of 2-level polytopes, cones, and configurations ⋮ Periodic triangulations of \(\mathbb{Z}^{n}\) ⋮ Metric embeddings of Laakso graphs into Banach spaces ⋮ Quadratic embedding constants of graph joins ⋮ Hyperbolic space has strong negative type ⋮ On the bond polytope ⋮ Lifting and separation procedures for the cut polytope ⋮ A nonlinear approach to dimension reduction ⋮ Isometric embeddings of snowflakes into finite-dimensional Banach spaces ⋮ Contact vectors of point lattices ⋮ An Improved Analysis of Local Search for Max-Sum Diversification ⋮ Total positivity in multivariate extremes ⋮ Classes of cut ideals and their Betti numbers ⋮ Optimal nonparametric testing of missing completely at random and its connections to compatibility ⋮ \(l_1\)-embeddability of shifted quadrilateral cylinder graphs ⋮ Generalized cut polytopes for binary hierarchical models ⋮ Inhomogeneous extreme forms ⋮ ON THE EDGE-CONNECTIVITY OF CARTESIAN PRODUCT GRAPHS ⋮ Cubic graphs, their Ehrhart quasi-polynomials, and a scissors congruence phenomenon ⋮ New Bell inequalities for the singlet state: Going beyond the Grothendieck bound ⋮ Delaunay polytopes derived from the Leech lattice ⋮ A guide to conic optimisation and its applications ⋮ Seminormality, canonical modules, and regularity of cut polytopes ⋮ A tight degree 4 sum-of-squares lower bound for the Sherrington-Kirkpatrick Hamiltonian ⋮ The hypermetric cone and polytope on eight vertices and some generalizations ⋮ On graphs of the cone decompositions for the min-cut and max-cut problems ⋮ GRAPHICAL MODELS FOR CORRELATED DEFAULTS ⋮ Support sets in exponential families and oriented matroid theory ⋮ Majorization and distances in trees ⋮ Exponential Lower Bounds for Polytopes in Combinatorial Optimization ⋮ On the bi-Lipschitz geometry of lamplighter graphs ⋮ Unavoidable minors for graphs with large \(\ell_p\)-dimension ⋮ The Running Intersection Relaxation of the Multilinear Polytope ⋮ Solving semidefinite programs using preconditioned conjugate gradients ⋮ Weakly Modular Graphs and Nonpositive Curvature ⋮ A proof of a conjecture by Haviv, Lyubashevsky and Regev on the second moment of a lattice Voronoi cell ⋮ Spectral bounds for the maximum cut problem ⋮ From Graph Orientation to the Unweighted Maximum Cut ⋮ Coarsening in algebraic multigrid using Gaussian processes ⋮ TESTING EMBEDDABILITY BETWEEN METRIC SPACES ⋮ Daisy cubes and distance cube polynomial ⋮ Sherali-adams strikes back ⋮ Hypercube emulation of interconnection networks topologies ⋮ Generalized network design polyhedra ⋮ OPTIMAL LOWER BOUND ON THE SUPREMAL STRICT p-NEGATIVE TYPE OF A FINITE METRIC SPACE ⋮ Unnamed Item ⋮ Ultrametricity of Dissimilarity Spaces and Its Significance for Data Mining ⋮ A Note on Seminormality of Cut Polytopes ⋮ Tight Cycle Relaxations for the Cut Polytope ⋮ Semi-supervised learning with regularized Laplacian

This page was built for publication: Geometry of cuts and metrics