Clique-Web Facets for Multicut Polytopes
From MaRDI portal
Publication:4027782
DOI10.1287/moor.17.4.981zbMath0762.90079OpenAlexW2164209543MaRDI QIDQ4027782
Martin Grötschel, Monique Laurent, Michel Marie Deza
Publication date: 1 March 1993
Published in: Mathematics of Operations Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1287/moor.17.4.981
Programming involving graphs or networks (90C35) Special polytopes (linear programming, centrally symmetric, etc.) (52B12)
Related Items
The partition problem, The clique partitioning problem: Facets and patching facets, Application of cut polyhedra. I, An overview of graph covering and partitioning, Facets of the \(k\)-partition polytope, An extended edge-representative formulation for the \(K\)-partitioning problem, Computational study of valid inequalities for the maximum \(k\)-cut problem, On the partial order polytope of a digraph, Exploiting sparsity for the min \(k\)-partition problem, Size-constrained graph partitioning polytopes, Binary Positive Semidefinite Matrices and Associated Integer Polytopes, The <scp>K‐partitioning</scp> problem: Formulations and <scp>branch‐and‐cut</scp>, New bounds for the \(\max\)-\(k\)-cut and chromatic number of a graph, A polyhedral study of lifted multicuts, Facets from gadgets, Binary positive semidefinite matrices and associated integer polytopes, The max-cut problem and quadratic 0-1 optimization; polyhedral aspects, relaxations and bounds, Facet-defining inequalities for the simple graph partitioning polytope, A two-level graph partitioning problem arising in mobile wireless communications, Projection results for the \(k\)-partition problem, Compositions in the bipartite subgraph polytope, Facets for the cut cone. II: Clique-web inequalities, The even and odd cut polytopes, Efficient semidefinite branch-and-cut for MAP-MRF inference, \(\{ 0,\frac12\}\)-Chvátal-Gomory cuts, Political districting to minimize cut edges, Collapsing and lifting for the cut cone
