Facet-defining inequalities for the simple graph partitioning polytope

DOI10.1016/j.disopt.2006.08.001zbMath1163.90804OpenAlexW2079197386MaRDI QIDQ2467133

Michael Malmros Sørensen

Publication date: 18 January 2008

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disopt.2006.08.001

zbMATH Keywords

clusteringgraph partitioningfacetpolyhedral combinatoricsmulticut

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items

An overview of graph covering and partitioning ⋮ An extended edge-representative formulation for the \(K\)-partitioning problem ⋮ Stochastic graph partitioning: quadratic versus SOCP formulations ⋮ Size-constrained graph partitioning polytopes ⋮ The <scp>K‐partitioning</scp> problem: Formulations and <scp>branch‐and‐cut</scp> ⋮ Solving graph partitioning on sparse graphs: cuts, projections, and extended formulations ⋮ Facets for node-capacitated multicut polytopes from path-block cycles with two common nodes ⋮ Improved compact formulations for a wide class of graph partitioning problems in sparse graphs ⋮ Political districting to minimize cut edges

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Facets of the clique partitioning polytope
• The discrete p-dispersion problem
• A cutting plane algorithm for a clustering problem
• Facets for the cut cone. I
• Facets for the cut cone. II: Clique-web inequalities
• The node capacitated graph partitioning problem: A computational study
• Lifting theorems and facet characterization for a class of clique partitioning inequalities
• A branch-and-cut algorithm for the equicut problem
• \(b\)-tree facets for the simple graph partitioning polytope
• Formulations and valid inequalities of the node capacitated graph partitioning problem
• Facets of the \(k\)-partition polytope
• Some new classes of facets for the equicut polytope
• The partition problem
• The equipartition polytope. I: Formulations, dimension and basic facets
• The equipartition polytope. II: Valid inequalities and facets
• Clique-Web Facets for Multicut Polytopes
• The clique partitioning problem: Facets and patching facets
• On the cut polytope
• On Linear Characterizations of Combinatorial Optimization Problems
• Efficient Algorithm for the Partitioning of Trees
• A Note on Clique-Web Facets for Multicut Polytopes
• Geometry of cuts and metrics