Clique-Web Facets for Multicut Polytopes

DOI10.1287/MOOR.17.4.981MaRDI QIDQ4027782zbMATH OpenOpenAlexFDO

Authors Martin Grötschel, Michel Deza, Monique Laurent

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

zbMATH Keywords

clique-web inequalitiescollapsingfacetsfacets of special polytopesliftingmulticut

Mathematics Subject Classification ID

Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Programming involving graphs or networks (90C35)

Recommendations

• A Note on Clique-Web Facets for Multicut Polytopes
• scientific article; zbMATH DE number 17641
• On the cut polytope
• Facets for the cut cone. II: Clique-web inequalities
• Facets for the cut cone. I

Cited in

(37)

• Clique facets of the axial and planar assignment polytopes
• The max-cut problem and quadratic 0-1 optimization; polyhedral aspects, relaxations and bounds
• Compositions in the bipartite subgraph polytope
• Facets for the cut cone. II: Clique-web inequalities
• Collapsing and lifting for the cut cone
• Computational study of valid inequalities for the maximum \(k\)-cut problem
• A two-level graph partitioning problem arising in mobile wireless communications
• Facets for node-capacitated multicut polytopes from path-block cycles with two common nodes
• Projection results for the \(k\)-partition problem
• Efficient semidefinite branch-and-cut for MAP-MRF inference
• \(\{ 0,\frac12\}\)-Chvátal-Gomory cuts
• Application of cut polyhedra. I
• Facets of the \(k\)-partition polytope
• On the partial order polytope of a digraph
• Political districting to minimize cut edges
• An overview of graph covering and partitioning
• Exploiting sparsity for the min \(k\)-partition problem
• Facets from gadgets
• The partition problem
• Facet-defining inequalities for the simple graph partitioning polytope
• A polyhedral study of lifted multicuts
• An extended edge-representative formulation for the \(K\)-partitioning problem
• Binary Positive Semidefinite Matrices and Associated Integer Polytopes
• scientific article; zbMATH DE number 15357 (Why is no real title available?)
• scientific article; zbMATH DE number 17641 (Why is no real title available?)
• scientific article; zbMATH DE number 1286488 (Why is no real title available?)
• The clique partitioning problem: Facets and patching facets
• A Note on Clique-Web Facets for Multicut Polytopes
• Size-constrained graph partitioning polytopes
• The <scp>K‐partitioning</scp> problem: Formulations and <scp>branch‐and‐cut</scp>
• \texttt{CP-Lib}: benchmark instances of the clique partitioning problem
• Binary positive semidefinite matrices and associated integer polytopes
• On the dominant of the multicut polytope
• The even and odd cut polytopes
• Chorded cycle facets of the clique partitioning polytope
• New facets of the clique partitioning polytope
• New bounds for the -k-cut and chromatic number of a graph

This page was built for publication: Clique-Web Facets for Multicut Polytopes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4027782)