The partition problem

DOI10.1007/BF01581239zbMath0774.90082OpenAlexW1993052292MaRDI 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

Programming involving graphs or networks (90C35) Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Integer programming (90C10)

Related Items

Planning personnel retraining: column generation heuristics, The clique partitioning problem: Facets and patching facets, Quasifibrations of graphs to find symmetries and reconstruct biological networks, An overview of graph covering and partitioning, Facets of the \(k\)-partition polytope, 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, Computational study of valid inequalities for the maximum \(k\)-cut problem, Cardinality constrained Boolean quadratic polytope, On the partial order polytope of a digraph, Solving group technology problems via clique partitioning, Exploiting sparsity for the min \(k\)-partition problem, Extended Graph Formulation for the Inequity Aversion Pricing Problem on Social Networks, An extended formulation of the convex recoloring problem on a tree, Size-constrained graph partitioning polytopes, A class of spectral bounds for max \(k\)-cut, Computational study of a branching algorithm for the maximum \(k\)-cut problem, The interval order polytope of a digraph, Efficient joint object matching via linear programming, A strong formulation for the graph partition problem, The <scp>K‐partitioning</scp> problem: Formulations and <scp>branch‐and‐cut</scp>, SOS-SDP: An Exact Solver for Minimum Sum-of-Squares Clustering, Orbitopal fixing, Solving graph partitioning on sparse graphs: cuts, projections, and extended formulations, Partitioning through projections: strong SDP bounds for large graph partition problems, New bounds for the \(\max\)-\(k\)-cut and chromatic number of a graph, On Integrality in Semidefinite Programming for Discrete Optimization, A polyhedral study of lifted multicuts, An Efficient Semidefinite Programming Relaxation for the Graph Partition Problem, Lagrangian relaxation versus genetic algorithm based metaheuristic for a large partitioning problem, A semidefinite relaxation based global algorithm for two-level graph partition problem, A branch-and-cut algorithm based on semidefinite programming for the minimum \(k\)-partition problem, New bounds and constraint propagation techniques for the clique partitioning problem, Optimal price zones of electricity markets: a mixed-integer multilevel model and global solution approaches, An exact approach for the multi-constraint graph partitioning problem, Facets from gadgets, Probabilistic Correlation Clustering and Image Partitioning Using Perturbed Multicuts, A branch-and-bound algorithm for solving max-\(k\)-cut problem, Block rearranging elements within matrix columns to minimize the variability of the row sums, Facet-defining inequalities for the simple graph partitioning polytope, A two-level graph partitioning problem arising in mobile wireless communications, Transitive packing, Branch-and-price-and-cut on the clique partitioning problem with minimum clique size requirement, Mixed-integer programming techniques for the connected max-\(k\)-cut problem, Projection results for the \(k\)-partition problem, Disconnecting graphs by removing vertices: a polyhedral approach, Global optimization of multilevel electricity market models including network design and graph partitioning, Unnamed Item, A branch-and-cut algorithm for the partitioning-hub location-routing problem, Improving the linear relaxation of maximum \(k\)-cut with semidefinite-based constraints, A Lagrangian Relaxation-Based Heuristic to Solve Large Extended Graph Partitioning Problems, Efficient semidefinite branch-and-cut for MAP-MRF inference, Cliques and clustering: A combinatorial approach, \(\{ 0,\frac12\}\)-Chvátal-Gomory cuts, Formulations and valid inequalities of the node capacitated graph partitioning problem, Scheduling Personnel Retraining: Column Generation Heuristics, Spectral bounds for graph partitioning with prescribed partition sizes, Congress seat allocation using mathematical optimization, Clustering of microarray data via clique partitioning, Lifting theorems and facet characterization for a class of clique partitioning inequalities, Political districting to minimize cut edges, Min-cut clustering

Cites Work