The partition problem
From MaRDI portal
The authors are dealing with two graph partitioning problems: \(\text{GPP1}(k)\): partition the node set \(V\) of a given graph \(G=(V,E)\) - - with edge weights \(C(e)\) -- into \(r\) subsets, so as to minimize the total weight of the edges with end points in two different subsets (i.e. the edgecuts) and \(r\leq k\) for a given integer \(k\). \(\text{GPP2}(k)\): partition the \(\dots\) and \(r\geq k\) for a given integer \(k\). Both problems are NP-complete. The paper gives integer programming formulations for both problems, identifies the dimensions of the associated polytopes and explores conditions under which certain kinds of inequalities (non-negativity, cycle inequality, clique inequality, wheel inequality, bicycle wheel inequality resp. for \(\text{GPP2}(k)\): spanning tree inequality, \(q\)-super-tree inequality, \(q\)-cycle-inequality, prism inequality) are facet defining.
Recommendations
- Facet-defining inequalities for the simple graph partitioning polytope
- Projection results for the \(k\)-partition problem
- Facets of the clique partitioning polytope
- The node capacitated graph partitioning problem: A computational study
- Formulations and valid inequalities of the node capacitated graph partitioning problem
Cites work
- A cutting plane algorithm for a clustering problem
- An Efficient Heuristic Procedure for Partitioning Graphs
- Clique-Web Facets for Multicut Polytopes
- Facets of the Bipartite Subgraph Polytope
- Facets of the clique partitioning polytope
- Graph theory with applications
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- On the cut polytope
- On the magnetisation of the ground states in two dimensional Ising spin glasses
- Scheduling to Minimize Interaction Cost
- The Complexity of Multiterminal Cuts
- The equipartition polytope. I: Formulations, dimension and basic facets
- The equipartition polytope. II: Valid inequalities and facets
Cited in
(91)- The solution to the partition reconstruction problem
- A polynomial characterization of some graph partitioning problems
- On a graph partition problem with application to VLSI layout
- Cliques and clustering: A combinatorial approach
- The node capacitated graph partitioning problem: A computational study
- Lifting theorems and facet characterization for a class of clique partitioning inequalities
- Min-cut clustering
- Cardinality constrained Boolean quadratic polytope
- Multiset graph partitioning
- Planning personnel retraining: column generation heuristics
- Computational study of valid inequalities for the maximum \(k\)-cut problem
- An extended formulation of the convex recoloring problem on a tree
- Lagrangian relaxation versus genetic algorithm based metaheuristic for a large partitioning problem
- Block rearranging elements within matrix columns to minimize the variability of the row sums
- A two-level graph partitioning problem arising in mobile wireless communications
- Projection results for the \(k\)-partition problem
- \(b\)-tree facets for the simple graph partitioning polytope
- Efficient semidefinite branch-and-cut for MAP-MRF inference
- \(\{ 0,\frac12\}\)-Chvátal-Gomory cuts
- Formulations and valid inequalities of the node capacitated graph partitioning problem
- Facets of the \(k\)-partition polytope
- The Knowlton-Graham partition problem
- On the partial order polytope of a digraph
- Global optimization of multilevel electricity market models including network design and graph partitioning
- Political districting to minimize cut edges
- An overview of graph covering and partitioning
- Exploiting sparsity for the min \(k\)-partition problem
- A class of spectral bounds for max \(k\)-cut
- An exact approach for the multi-constraint graph partitioning problem
- Facets from gadgets
- A branch-and-bound algorithm for solving max-\(k\)-cut problem
- Mixed-integer programming techniques for the connected max-\(k\)-cut problem
- Improving the linear relaxation of maximum \(k\)-cut with semidefinite-based constraints
- Spectral bounds for graph partitioning with prescribed partition sizes
- Congress seat allocation using mathematical optimization
- New bounds and constraint propagation techniques for the clique partitioning problem
- Facet-defining inequalities for the simple graph partitioning polytope
- Branch-and-price-and-cut on the clique partitioning problem with minimum clique size requirement
- Clustering of microarray data via clique partitioning
- The equipartition polytope. I: Formulations, dimension and basic facets
- Computational study of a branching algorithm for the maximum \(k\)-cut problem
- A polyhedral study of lifted multicuts
- A semidefinite relaxation based global algorithm for two-level graph partition problem
- Separation of partition inequalities
- A Lagrangian relaxation-based heuristic to solve large extended graph partitioning problems
- Scheduling personnel retraining: column generation heuristics
- An efficient semidefinite programming relaxation for the graph partition problem
- Partition inequalities: separation, extensions, and network design
- Separation algorithm for tree partitioning inequalities
- An extended edge-representative formulation for the \(K\)-partitioning problem
- Probabilistic correlation clustering and image partitioning using perturbed multicuts
- Stochastic graph partitioning: quadratic versus SOCP formulations
- Multicuts and perturb \& MAP for probabilistic graph clustering
- Polyhedral combinatorics of the \(K\)-partitioning problem with representative variables
- On the Graph Bisection Cut Polytope
- scientific article; zbMATH DE number 1193306 (Why is no real title available?)
- Orbitopal fixing
- The Graph Partitioning Polytope on Series-Parallel and 4-Wheel Free Graphs
- The clique partitioning problem: Facets and patching facets
- Optimal price zones of electricity markets: a mixed-integer multilevel model and global solution approaches
- Transitive packing
- Some efficiently solvable problems over integer partition polytopes
- Quasifibrations of graphs to find symmetries and reconstruct biological networks
- Determining an estimate of an equivalence relation for moderate and large sized sets
- Extended Graph Formulation for the Inequity Aversion Pricing Problem on Social Networks
- The interval order polytope of a digraph
- SOS-SDP: An Exact Solver for Minimum Sum-of-Squares Clustering
- Disconnecting graphs by removing vertices: a polyhedral approach
- Efficient joint object matching via linear programming
- A strong formulation for the graph partition problem
- 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
- Partitioning through projections: strong SDP bounds for large graph partition problems
- On Integrality in Semidefinite Programming for Discrete Optimization
- A branch-and-cut algorithm based on semidefinite programming for the minimum \(k\)-partition problem
- \texttt{CP-Lib}: benchmark instances of the clique partitioning problem
- Coordinated \textit{seru} scheduling and distribution operation problems with DeJong's learning effects
- Integer programming models and polyhedral study for the geodesic classification problem on graphs
- Chorded cycle facets of the clique partitioning polytope
- Two-phase GRASP for the multi-constraint graph partitioning problem
- New facets of the clique partitioning polytope
- A graph multi-separator problem for image segmentation
- Optimizing connected components graph partitioning with minimum size constraints using integer programming and spectral clustering techniques
- Branch and cut for partitioning a graph into a cycle of clusters
- A branch-and-cut algorithm for the partitioning-hub location-routing problem
- Multilevel iterated tabu search for the multi-constraint graph partitioning problem
- Facets of the clique partitioning polytope
- The mean-partition problem
- Solving group technology problems via clique partitioning
- New bounds for the -k-cut and chromatic number of a graph
This page was built for publication: The partition problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2366610)
