Clique-Web Facets for Multicut Polytopes
The authors are concerned with facets of special polytopes which are induced by some \(k\)-partition \(V=V_ 1+\cdots+ V_ k\) of the set of vertices of a given graph \(G=(V,E)\) in the following way: a multicut is an edge set, where each edge connects two different parts of \(V\). The polytopes now are the convex hulls of the incidence vectors of all multicuts with at most \(k\) shores (respectively at least \(k\) shores) of the complete graph \(K_ n\): \(MC_ k(n)\) (resp. \(MC_{\geq k}(n))\). For given integers \(n\), \(p\), \(q\) and \(r\) with \(n=p+q\), \(p-q\geq 2r+1\) clique-web inequalities are introduced and it is shown that they are valid for the multicut polytope \(MC_ k(n)\). The parameter values are rigorously classified with respect to be facet-inducing for \(MC_ k(n)\) resp. \(MC_{\geq k}(n)\). The operations `collapsing' and `lifting' are extended to multicuts and yield new classes of facets too.
- 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)
