Polyhedral combinatorics of the K-partitioning problem with representative variables

DOI10.1016/J.DAM.2016.04.002MaRDI QIDQ335322zbMATHOpenAlexFDO

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

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)

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

Cites work

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

Cited in

(14)

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

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)