The partition problem

DOI10.1007/BF01581239zbMath0774.90082MaRDI QIDQ2366610

Publication date: 30 August 1993

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01581239

zbMATH Keywords

spanning tree; graph partitioning; facet defining cuts; cycle inequality; clique inequality

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

52B12: Special polytopes (linear programming, centrally symmetric, etc.)

90C10: Integer programming

Related Items

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, Unnamed Item, Quasifibrations of graphs to find symmetries and reconstruct biological networks, 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, Solving graph partitioning on sparse graphs: cuts, projections, and extended formulations, Partitioning through projections: strong SDP bounds for large graph partition problems, Separation algorithm for tree partitioning inequalities, An extended edge-representative formulation for the \(K\)-partitioning problem, 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, Orbitopal fixing, Size-constrained graph partitioning polytopes, A branch-and-cut algorithm based on semidefinite programming for the minimum \(k\)-partition problem, A branch-and-cut algorithm for the partitioning-hub location-routing problem, Solving group technology problems via clique partitioning, New bounds for the \(\max\)-\(k\)-cut and chromatic number of a graph, Cliques and clustering: A combinatorial approach, Lifting theorems and facet characterization for a class of clique partitioning inequalities, Min-cut clustering, Cardinality constrained Boolean quadratic polytope, 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, 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, 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, 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, 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, Probabilistic Correlation Clustering and Image Partitioning Using Perturbed Multicuts

Cites Work