A branch-and-cut algorithm based on semidefinite programming for the minimum \(k\)-partition problem
From MaRDI portal
Publication:646707
DOI10.1007/s10479-008-0481-4zbMath1225.90144OpenAlexW1994932713MaRDI QIDQ646707
Frauke Liers, Miguel F. Anjos, Bissan Ghaddar
Publication date: 17 November 2011
Published in: Annals of Operations Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10479-008-0481-4
Programming involving graphs or networks (90C35) Semidefinite programming (90C22) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)
Related Items
SDP-based bounds for graph partition via extended ADMM, A computational study for bilevel quadratic programs using semidefinite relaxations, An extended edge-representative formulation for the \(K\)-partitioning problem, Computational study of valid inequalities for the maximum \(k\)-cut problem, Conic approximation to quadratic optimization with linear complementarity constraints, Exploiting sparsity for the min \(k\)-partition problem, On semidefinite programming relaxations of maximum \(k\)-section, Computational study of a branching algorithm for the maximum \(k\)-cut problem, SOS-SDP: An Exact Solver for Minimum Sum-of-Squares Clustering, Orbitopal fixing, New bounds for the \(\max\)-\(k\)-cut and chromatic number of a graph, An Efficient Semidefinite Programming Relaxation for the Graph Partition Problem, A semidefinite relaxation based global algorithm for two-level graph partition problem, A branch-and-bound algorithm for solving max-\(k\)-cut problem, Combining clustered adaptive multistart and discrete dynamic convexized method for the max-cut problem, A framework for solving mixed-integer semidefinite programs, An Iterative Scheme for Valid Polynomial Inequality Generation in Binary Polynomial Programming, A two-level graph partitioning problem arising in mobile wireless communications, A multiple search operator heuristic for the max-k-cut problem, Projection results for the \(k\)-partition problem, A branch‐and‐price approach to k‐clustering minimum biclique completion problem, Improving the linear relaxation of maximum \(k\)-cut with semidefinite-based constraints, Semidefinite relaxations for partitioning, assignment and ordering problems, SDP Relaxations for Some Combinatorial Optimization Problems, Computational Approaches to Max-Cut, Robust Critical Node Selection by Benders Decomposition, Semidefinite relaxations for partitioning, assignment and ordering problems, New Formulations for the Conflict Resolution Problem in the Scheduling of Television Commercials
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION
- The max-cut problem and quadratic 0-1 optimization; polyhedral aspects, relaxations and bounds
- Solving quadratic (0,1)-problems by semidefinite programs and cutting planes
- Minimizing breaks by maximizing cuts.
- Graph partitioning using linear and semidefinite programming
- On approximate graph colouring and MAX-\(k\)-CUT algorithms based on the \(\vartheta\)-function
- Facets of the \(k\)-partition polytope
- The partition problem
- An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
- On the Shannon capacity of a graph
- New $\frac{3}{4}$-Approximation Algorithms for the Maximum Satisfiability Problem
- Realignment in the National Football League: Did they do it right?
- CSDP, A C library for semidefinite programming
- On the cut polytope
- Orbitopal Fixing
- A Branch and Bound Algorithm for Max-Cut Based on Combining Semidefinite and Polyhedral Relaxations
- Geometry of cuts and metrics
