Facets of the k-partition polytope

DOI10.1016/0166-218X(93)E0175-XzbMATH Open0835.90075OpenAlexW2063117516WikidataQ126819253 ScholiaQ126819253MaRDI QIDQ1897366FDOQ1897366

Authors: 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

Recommendations

• Lifting facets of the cut polytope
• Clique-Web Facets for Multicut Polytopes
• Collapsing and lifting for the cut cone
• Facets for the cut cone. I
• On the Linear Description of the k-cycle Polytope

zbMATH Keywords

convex hullliftingcomplete graphcut polytopevalid inequalityanti-web inequalityfacets of the \(k\)-partition polytope

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (28)

• Facet-defining inequalities for the simple graph partitioning polytope
• Computational study of a branching algorithm for the maximum \(k\)-cut problem
• An overview of graph covering and partitioning
• Signed orders, choice probabilities, and linear polytopes
• Spectral bounds for graph partitioning with prescribed partition sizes
• A two-level graph partitioning problem arising in mobile wireless communications
• Global optimization of multilevel electricity market models including network design and graph partitioning
• 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
• The minimum chromatic violation problem: a polyhedral study
• A class of spectral bounds for max \(k\)-cut
• A branch-and-bound algorithm for solving max-\(k\)-cut problem
• Projection results for the \(k\)-partition problem
• Improving the linear relaxation of maximum \(k\)-cut with semidefinite-based constraints
• Computational study of valid inequalities for the maximum \(k\)-cut problem
• Orbitopal fixing
• Cardinality constrained Boolean quadratic polytope
• A polyhedral study of lifted multicuts
• Stochastic graph partitioning: quadratic versus SOCP formulations
• On factorization of multiparticle pentagons
• A branch-and-cut algorithm based on semidefinite programming for the minimum \(k\)-partition problem
• Exploiting sparsity for the min \(k\)-partition problem
• The minimum chromatic violation problem: a polyhedral approach
• Optimal price zones of electricity markets: a mixed-integer multilevel model and global solution approaches
• Facets of the weak order polytope derived from the induced partition projection
• A semidefinite relaxation based global algorithm for two-level graph partition problem
• Number of Vertices of the Polytope of Integer Partitions and Factorization of the Partitioned Number
• Political districting to minimize cut edges

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

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