Geometry of cuts and metrics

Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Research exposition (monographs, survey articles) pertaining to convex and discrete geometry (52-02)

Related Items

The realization problem for tail correlation functions, \texttt{mplrs}: a scalable parallel vertex/facet enumeration code, Infinite series of extreme Delaunay polytopes, Characterizations of pseudo-codewords of (low-density) parity-check codes, The multi-layered network design problem, Linearly independent split systems, Vašek Chvátal: a very short introduction (on the occasion of his 60th birthday), The robust network loading problem with dynamic routing, $t$-copula from the viewpoint of tail dependence matrices, New classes of facets of the cut polytope and tightness of $I_{mm22}$ Bell inequalities, On computational capabilities of Ising machines based on nonlinear oscillators, Kantorovich distance on finite metric spaces: Arens-Eells norm and CUT norms, Improved exact approaches for row layout problems with departments of equal length, LP and SDP branch-and-cut algorithms for the minimum graph bisection problem: a computational comparison, High-dimensional change-point estimation: combining filtering with convex optimization, Addendum to: ``Lattices from equiangular tight frames, On finding convex cuts in general, bipartite and plane graphs, Boolean quadric polytopes are faces of linear ordering polytopes, Exact solution of the 2-dimensional grid arrangement problem, The convex geometry of linear inverse problems, A note on the 2-circulant inequalities for the MAX-cut problem, Metric transforms yielding Gromov hyperbolic spaces, Retracts and algebraic properties of cut algebras, Exact semidefinite formulations for a class of (random and non-random) nonconvex quadratic programs, On tail dependence matrices. The realization problem for parametric families, On partial cubes, well-graded families and their duals with some applications in graphs, Functorial hierarchical clustering with overlaps, Bidirectional comparison of multi-attribute qualitative objects, Minimal webs in Riemannian manifolds, Metric characterization of apartments in dual polar spaces, COMs: complexes of oriented matroids, Unbounded convex sets for non-convex mixed-integer quadratic programming, On the establishment of distinct identities in overlay networks, Lexicographic and reverse lexicographic quadratic Gröbner bases of cut ideals, Counting linear extensions of restricted posets, Isotropic covariance functions on graphs and their edges, Convex and concave envelopes: revisited and new perspectives, A note on representations of linear inequalities in non-convex mixed-integer quadratic programs, Polyhedral conditions for the nonexistence of the MLE for hierarchical log-linear models, A counterexample to the dominating set conjecture, Valid inequalities for quadratic optimisation with domain constraints, Cut polytope has vertices on a line, Generating facets for the cut polytope of a graph by triangular elimination, Facet-defining inequalities for the simple graph partitioning polytope, On some factorizations of semi-metric cones and quality estimates of heuristic metrics in data analysis problems, Variations of a combinatorial problem on finite sets, Metric inequalities and the network loading problem, On the Lovász theta function and some variants, A new graph parameter related to bounded rank positive semidefinite matrix completions, Distance spectra of graphs: a survey, An analog of the Cook theorem for polytopes, Isometric embedding of Busemann surfaces into $L_1$, Euclidean quotients of finite metric spaces, $k$-neighborly faces of the Boolean quadric polytopes, The common face of some 0/1-polytopes with NP-complete nonadjacency relation, $M$-convex functions and tree metrics, On a recognition problem on cut polytope relaxations, Global optimization of multilevel electricity market models including network design and graph partitioning, Exploring the relationship between max-cut and stable set relaxations, On simplicial and cubical complexes with short links, Nonembeddability theorems via Fourier analysis, Small cones of $m$-hemimetrics, Roundness properties of groups., The isometries of the cut, metric and hypermetric cones, Embeddability of open-ended carbon nanotubes in hypercubes, $\Theta$-graceful labelings of partial cubes, Gromov product structures, quadrangle structures and split metric decompositions for finite metric spaces, Max-multiflow/min-multicut for G+H series-parallel, Completely positive semidefinite rank, A semidefinite programming based polyhedral cut and price approach for the maxcut problem, Stolarsky's invariance principle for projective spaces, An upper bound for a valence of a face in a parallelohedral tiling, Learning algebraic varieties from samples, Membership testing for Bernoulli and tail-dependence matrices, Efficient semidefinite branch-and-cut for MAP-MRF inference, Injective metrizability and the duality theory of cubings, Variational approximation of interface energies and applications, A binarisation heuristic for non-convex quadratic programming with box constraints, Volume computation for sparse Boolean quadric relaxations, On density of subgraphs of halved cubes, Covering aspects of the Niemeier lattices, Channel metrization, Graphs and spherical two-distance sets, On fractional cut covers, The six-dimensional Delaunay polytopes, Admissible Bernoulli correlations, Lattices from tight frames and vertex transitive graphs, The solution polyhedron of the dissipative inequality for relaxation SISO systems, Maximal margin classification for metric spaces, Dykstra's algorithm with strategies for projecting onto certain polyhedral cones, Kissing numbers for balls with varying radii, Least-distortion Euclidean embeddings of graphs: Products of cycles and expanders, A new separation algorithm for the Boolean quadric and cut polytopes, Distance geometry for kissing spheres, A direct proof that $\ell_\infty^{(3)}$ has generalized roundness zero, Strengthened semidefinite relaxations via a second lifting for the Max-Cut problem, The reverse Hlawka inequality in a Minkowski space, The simplest families of polytopes associated with NP-hard problems, Fast method for verifying Chernikov rules in Fourier-Motzkin elimination, Complete positivity and distance-avoiding sets, On the structure of the tight-span of a totally split-decomposable metric, There are no finite partial cubes of girth more than 6 and minimum degree at least 3, On the diameter of cut polytopes, On cell matrices: a class of Euclidean distance matrices, On the directed cut cone and polytope, Hypercubes are determined by their distance spectra, Toric geometry of cuts and splits, Zero-one completely positive matrices and the $\mathcal A(R, S)$ classes, The distance spectrum and energy of the compositions of regular graphs, Antipodal metrics and split systems, Extremal positive semidefinite matrices whose sparsity pattern is given by graphs without $K_{5}$ minors, Solving Max-cut to optimality by intersecting semidefinite and polyhedral relaxations, Coarse differentiation and multi-flows in planar graphs, On rotational symmetries of drawings of coherent periodic graphs, Finite metrics in switching classes, A group majorization ordering for Euclidean distance matrices, Semidefinite programming in combinatorial optimization, Cuts, matrix completions and graph rigidity, Realization of metric spaces as inverse limits, and bilipschitz embedding in $L_1$, A computational study and survey of methods for the single-row facility layout problem, Flow metrics, How to compute the rank of a Delaunay polytope, Lattice Delone simplices with super-exponential volume, Metrization of weighted graphs, Positive definite metric spaces, Partial cubes and their $\tau$-graphs, Transitive actions of finite Abelian groups of sup-norm isometries, Compressed polytopes and statistical disclosure limitation, On a class of metrics related to graph layout problems, The contact polytope of the Leech lattice, A polyhedral approach to the single row facility layout problem, Distance covariance in metric spaces, $l_1$-embeddability under the edge-gluing operation on graphs, Small bipartite subgraph polytopes, On the polyhedral structure of uniform cut polytopes, Gap inequalities for non-convex mixed-integer quadratic programs, Computing the Grothendieck constant of some graph classes, A semidefinite optimization approach to the target visitation problem, New bounds for the $\max$-$k$-cut and chromatic number of a graph, Interval routing in some planar networks., Isometric embeddings of subdivided wheels in hypercubes, Compression bounds for Lipschitz maps from the Heisenberg group to $L_{1}$, A class of hypergraphs and vertices of cut polytope relaxations, A class of graph-geodetic distances generalizing the shortest-path and the resistance distances, The walk distances in graphs, Solving survivable two-layer network design problems by metric inequalities, The split decomposition of a $k$-dissimilarity map, Complexity results for the gap inequalities for the max-cut problem, A lexicographic semiorder polytope and probabilistic representations of choice, A branch-and-cut algorithm based on semidefinite programming for the minimum $k$-partition problem, Cubic inflation, mirror graphs, regular maps, and partial cubes, A QPTAS for TSP with fat weakly disjoint neighborhoods in doubling metrics, Enhanced negative type for finite metric trees, Cut ideals of $K_{4}$-minor free graphs are generated by quadrics, Geometricity of genetic operators for real-coded representation, Metric characterizations of superreflexivity in terms of word hyperbolic groups and finite graphs, Embedding into $l_{\infty }^{2}$ is easy, embedding into $l_{\infty}^{3}$ is NP-complete, Cubical token systems, Voronoi polytopes for polyhedral norms on lattices, Media theory: Representations and examples, The 22 minimal dichotomy decompositions of the $K_5$-distance, On reduced semidefinite programs for second order moment bounds with applications, Correctness criteria for algebraic closures of the estimate-calculating algorithm model, A new approach to low-distortion embeddings of finite metric spaces into non-superreflexive Banach spaces, Bourgain's discretization theorem, From equipartition to uniform cut polytopes: extended polyhedral results, Embedding into the rectilinear plane in optimal $O(n^{2})$ time, Infinite serie of extreme Delaunay polytopes, Differentiating maps into $L^1$, and the geometry of BV functions, Strict $p$-negative type of a metric space, The graph bottleneck identity, New semidefinite programming relaxations for the linear ordering and the traveling salesman problem, Partial cubes: Structures, characterizations, and constructions, Forbidden minor characterizations for low-rank optimal solutions to semidefinite programs over the elliptope, Delaunay and Voronoi polytopes of the root lattice $E_{7}$ and of the dual lattice $E^\ast_{7}$, A study of the quadratic semi-assignment polytope, On the extension complexity of combinatorial polytopes, The decomposition of the hypermetric cone into $L$-domains, Subdivided graphs as isometric subgraphs of Hamming graphs, Optimal realizations of generic five-point metrics, A linearization framework for unconstrained quadratic (0-1) problems, Asymmetric distances, semidirected networks and majority in Fermat-Weber problems, A prolongation-projection algorithm for computing the finite real variety of an ideal, The edge-weighted clique problem: Valid inequalities, facets and polyhedral computations, An improved Benders decomposition applied to a multi-layer network design problem, Solving quadratic (0,1)-problems by semidefinite programs and cutting planes, Transitive, locally finite median graphs with finite blocks, Tight spans of distances and the dual fractionality of undirected multiflow problems, Extended formulations for convex hulls of some bilinear functions, Two-dimensional partial cubes, Decomposition and $l_1$-embedding of weakly median graphs, Quasi-semi-metrics, oriented multi-cuts and related polyhedra, Uniform partitions of 3-space, their relatives and embedding, A classification of the six-point prime metrics, Fullerenes and coordination polyhedra versus half-cube embeddings, Relaxation optical bistability: A new class of optically bistable elements, Clusters of cycles, About Lagrangian methods in integer optimization, Seriation in the presence of errors: NP-hardness of $l_{\infty}$-fitting Robinson structures to dissimilarity matrices, An algorithm for computing cutpoints in finite metric spaces, Mixed-integer programming techniques for the minimum sum-of-squares clustering problem, First-order logic axiomatization of metric graph theory, Cycle algebras and polytopes of matroids, Remarks on non linear type and Pisiers inequality, Proper actions of wreath products and generalizations, On handling cutting planes in interior-point methods for solving semi-definite relaxations of binary quadratic optimization problems, Sparktope: linear programs from algorithms, A Polytope for a Product of Real Linear Functions in 0/1 Variables, Approximation Limits of Linear Programs (Beyond Hierarchies), Minkowski Geometry—Some Concepts and Recent Developments, Normal binary graph models, Gorenstein cut polytopes, Determining finite connected graphs along the quadratic embedding constants of paths, The Ratio-Cut Polytope and K-Means Clustering, Speeding up IP-based algorithms for constrained quadratic 0-1 optimization, Small Cones of Oriented Semi-Metrics, Does negative type characterize the round sphere?, Negative-type diversities, a multi-dimensional analogue of negative-type metrics, Unnamed Item, Necessary conditions for extended noncontextuality in general sets of random variables, Generalised 2-circulant inequalities for the max-cut problem, A cut-and-branch algorithm for the quadratic knapsack problem, Trigonometric approximation of the max-cut polytope is star-like, Hierarchical Models, Marginal Polytopes, and Linear Codes, Magnitude and Holmes–Thompson intrinsic volumes of convex bodies, The Bipartite Boolean Quadric Polytope with Multiple-Choice Constraints, Fuzzy compatibility relations and pseudo-monometrics: some correspondences, A Comparative Study of Linear and Semidefinite Branch-and-Cut Methods for Solving the Minimum Graph Bisection Problem, Binary Positive Semidefinite Matrices and Associated Integer Polytopes, Hypercube embeddings and Cayley graphs generated by transpositions, Entanglement of free fermions on Johnson graphs, Graph partitioning: an updated survey, Wasserstein distance and metric trees, Dimension reduction for maximum matchings and the fastest mixing Markov chain, Labelings vs. embeddings: on distributed and prioritized representations of distances, The arithmetic topology of genetic alignments, Distance-regular graphs with exactly one positive $q$-distance eigenvalue, Diversities and the generalized circumradius, Complexity of combinatorial optimization problems in terms of face lattices of associated polytopes, Tail-dependence, exceedance sets, and metric embeddings, On generalized discrete metric structures, A Hierarchy of Subgraph Projection-Based Semidefinite Relaxations for Some NP-Hard Graph Optimization Problems, Graphical designs and gale duality, Factorization and pseudofactorization of weighted graphs, Expander graphs and their applications, The Excluded Minors for Isometric Realizability in the Plane, Unnamed Item, Isometric Hamming embeddings of weighted graphs, Recent Developments in Discrete Convex Analysis, Euclidean distortion and the sparsest cut, Semidefinite Approximation of Closed Convex Set, A PTAS for the Steiner Forest Problem in Doubling Metrics, ARITHMETIC ASPECTS OF SYMMETRIC EDGE POLYTOPES, Encoding Binary Neural Codes in Networks of Threshold-Linear Neurons, Optimal price zones of electricity markets: a mixed-integer multilevel model and global solution approaches, On the Distortion of Locality Sensitive Hashing, Correlation matrices, Clifford algebras, and completely positive semidefinite rank, The Riemannian and Affine Geometry of Facial Expression and Action Recognition, Leggett-Garg inequalities and the geometry of the cut polytope, Comparison of Metric Spectral Gaps, Constructing test functions for global optimization using continuous formulations of graph problems, A Unified Approach to Mixed-Integer Optimization Problems With Logical Constraints, Approximating Requirement Cut via a Configuration LP, The Hypermetric Cone on Seven Vertices, Compression bounds for wreath products, Basis problem for turbulent actions. I: Tsirelson submeasures, Tangent Halfspaces to Sets of Finite Perimeter in Carnot Groups, Principal majorization ideals and optimization, On 0-1 polytopes with many facets, Unnamed Item, Complexity and algorithms for computing Voronoi cells of lattices, On the binary solitaire cone, Two theorems on Euclidean distance matrices and Gale transform, Image Labeling Based on Graphical Models Using Wasserstein Messages and Geometric Assignment, Inapproximability for metric embeddings into $\mathbb{R}^{d}$, Explicit Construction of the Voronoi and Delaunay Cells of W(An) and W(Dn) Lattices and Their Facets, Some inequalities for central moments of matrices, Recent Progress in Interior-Point Methods: Cutting-Plane Algorithms and Warm Starts, Computational Approaches to Max-Cut, Global Approaches for Facility Layout and VLSI Floorplanning, Coloring the Voronoi tessellation of lattices, The Andoni–Krauthgamer–Razenshteyn Characterization of Sketchable Norms Fails for Sketchable Metrics, Expanders with respect to Hadamard spaces and random graphs, A Tractable Class of Binary VCSPs via M-Convex Intersection, POINT DISTRIBUTIONS IN TWO‐POINT HOMOGENEOUS SPACES, FINITE FLAT SPACES, Solving LP Relaxations of Some NP-Hard Problems Is As Hard As Solving Any Linear Program, Strict Complementarity in Semidefinite Optimization with Elliptopes Including the MaxCut SDP, Binary Component Decomposition Part I: The Positive-Semidefinite Case, The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative-Type Metrics into ℓ ₁, Scaling entropy and automorphisms with pure point spectrum, Threshold Dynamics for Networks with Arbitrary Surface Tensions, Engineering Branch-and-Cut Algorithms for the Equicut Problem, Complexity of the Positive Semidefinite Matrix Completion Problem with a Rank Constraint, Global convergence of the alternating projection method for the Max-Cut relaxation problem, Quasisymmetric embeddings, the observable diameter, and expansion properties of graphs, Unnamed Item, New approaches for optimizing over the semimetric polytope, On the canonical metric representation, average distance, and partial Hamming graphs, FRAÏSSÉ LIMITS FOR RELATIONAL METRIC STRUCTURES, Accelerating Fourier–Motzkin elimination using bit pattern trees, Affine maps between quadratic assignment polytopes and subgraph isomorphism polytopes