Facets of the \(k\)-partition polytope

DOI10.1016/0166-218X(93)E0175-XzbMath0835.90075OpenAlexW2063117516WikidataQ126819253 ScholiaQ126819253MaRDI QIDQ1897366

Yanyan Li

Publication date: 22 October 1995

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0166-218x(93)e0175-x

zbMATH Keywords

liftingconvex hullcut polytopecomplete graphvalid inequalityanti-web inequalityfacets of the \(k\)-partition polytope

Mathematics Subject Classification ID

Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Combinatorial optimization (90C27)

Related Items (25)

An overview of graph covering and partitioning ⋮ Stochastic graph partitioning: quadratic versus SOCP formulations ⋮ Computational study of valid inequalities for the maximum \(k\)-cut problem ⋮ Cardinality constrained Boolean quadratic polytope ⋮ Exploiting sparsity for the min \(k\)-partition problem ⋮ A class of spectral bounds for max \(k\)-cut ⋮ The minimum chromatic violation problem: a polyhedral study ⋮ Computational study of a branching algorithm for the maximum \(k\)-cut problem ⋮ The minimum chromatic violation problem: a polyhedral approach ⋮ The <scp>K‐partitioning</scp> problem: Formulations and <scp>branch‐and‐cut</scp> ⋮ Orbitopal fixing ⋮ New bounds for the \(\max\)-\(k\)-cut and chromatic number of a graph ⋮ A polyhedral study of lifted multicuts ⋮ A semidefinite relaxation based global algorithm for two-level graph partition problem ⋮ A branch-and-cut algorithm based on semidefinite programming for the minimum \(k\)-partition problem ⋮ Optimal price zones of electricity markets: a mixed-integer multilevel model and global solution approaches ⋮ A branch-and-bound algorithm for solving max-\(k\)-cut problem ⋮ 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 ⋮ Global optimization of multilevel electricity market models including network design and graph partitioning ⋮ Improving the linear relaxation of maximum \(k\)-cut with semidefinite-based constraints ⋮ Spectral bounds for graph partitioning with prescribed partition sizes ⋮ Political districting to minimize cut edges ⋮ Signed orders, choice probabilities, and linear polytopes

Cites Work

• Unnamed Item
• Facets of the clique partitioning polytope
• On the cycle polytope of a binary matroid
• The Boolean quadratic polytope: Some characteristics, facets and relatives
• Weakly bipartite graphs and the max-cut problem
• Facets for the cut cone. I
• Facets for the cut cone. II: Clique-web inequalities
• Collapsing and lifting for the cut cone
• The partition problem
• The equipartition polytope. II: Valid inequalities and facets
• Facets of the Bipartite Subgraph Polytope
• Clique-Web Facets for Multicut Polytopes
• On the cut polytope

This page was built for publication: Facets of the \(k\)-partition polytope