Polyhedral combinatorics of the K-partitioning problem with representative variables

DOI10.1016/J.DAM.2016.04.002zbMATH Open1348.05160OpenAlexW2346810955MaRDI QIDQ335322FDOQ335322

Authors: Zacharie Ales, Arnaud Knippel, Alexandre Pauchet 

Publication date: 2 November 2016

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

Full work available at URL: https://doi.org/10.1016/j.dam.2016.04.002

Recommendations

• An extended edge-representative formulation for the \(K\)-partitioning problem
• Projection results for the \(k\)-partition problem
• The partition problem
• Facets of the \(k\)-partition polytope
• Facet-defining inequalities for the simple graph partitioning polytope

zbMATH Keywords

combinatorial optimizationgraph partitioningpolyhedral approach

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Signed and weighted graphs (05C22) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Network flows. Theory, algorithms, and applications.
• An Efficient Heuristic Procedure for Partitioning Graphs
• Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
• Some simplified NP-complete graph problems
• On the cut polytope
• On the asymmetric representatives formulation for the vertex coloring problem
• A cutting plane algorithm for a clustering problem
• Branch-and-price-and-cut on the clique partitioning problem with minimum clique size requirement
• The clique partitioning problem: Facets and patching facets
• Facets of the clique partitioning polytope
• The node capacitated graph partitioning problem: A computational study
• Min-cut clustering
• Formulations and valid inequalities of the node capacitated graph partitioning problem
• An exact algorithm for graph partitioning
• The partition problem
• On the solution of a graph partitioning problem under capacity constraints
• Orbitopal fixing
• Size-constrained graph partitioning polytopes
• Lifting theorems and facet characterization for a class of clique partitioning inequalities
• On the partial order polytope of a digraph
• Linear and quadratic programming approaches for the general graph partitioning problem
• The equipartition polytope. I: Formulations, dimension and basic facets
• Polyhedral combinatorics of the \(K\)-partitioning problem with representative variables
• Realignment in the National Football League: Did they do it right?

Cited In (11)

• An overview of graph covering and partitioning
• A modeling and computational study of the frustration index in signed networks
• The sport teams grouping problem
• Efficient enumeration of the optimal solutions to the correlation clustering problem
• A two-level graph partitioning problem arising in mobile wireless communications
• The <scp>K‐partitioning</scp> problem: Formulations and <scp>branch‐and‐cut</scp>
• Connected graph partitioning with aggregated and non‐aggregated gap objective functions
• Polyhedral combinatorics of the \(K\)-partitioning problem with representative variables
• Integer programming formulations and efficient local search for relaxed correlation clustering
• A branch-and-cut algorithm for the maximum \(k\)-balanced subgraph of a signed graph
• Improved compact formulations for a wide class of graph partitioning problems in sparse graphs

This page was built for publication: Polyhedral combinatorics of the \(K\)-partitioning problem with representative variables

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