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-4zbMATH Open1225.90144OpenAlexW1994932713MaRDI QIDQ646707FDOQ646707
Authors: Bissan Ghaddar, Miguel F. Anjos, F. Liers 
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
Recommendations
- Solving \(k\)-way graph partitioning problems to optimality: the impact of semidefinite relaxations and the bundle method
- Computational study of a branching algorithm for the maximum \(k\)-cut problem
- Computational results of a semidefinite branch-and-bound algorithm for \(k\)-cluster
- Solving \(k\)-cluster problems to optimality with semidefinite programming
- scientific article; zbMATH DE number 3991298
Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Semidefinite programming (90C22)
Cites Work
- CSDP, A C library for semidefinite programming
- On the Shannon capacity of a graph
- Geometry of cuts and metrics
- Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION
- The max-cut problem and quadratic 0-1 optimization; polyhedral aspects, relaxations and bounds
- An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
- On the cut polytope
- Title not available (Why is that?)
- New $\frac{3}{4}$-Approximation Algorithms for the Maximum Satisfiability Problem
- The partition problem
- Solving quadratic (0,1)-problems by semidefinite programs and cutting planes
- Facets of the \(k\)-partition polytope
- Realignment in the National Football League: Did they do it right?
- A Branch and Bound Algorithm for Max-Cut Based on Combining Semidefinite and Polyhedral Relaxations
- Graph partitioning using linear and semidefinite programming
- Minimizing breaks by maximizing cuts.
- Title not available (Why is that?)
- Orbitopal Fixing
- On approximate graph colouring and MAX-\(k\)-CUT algorithms based on the \(\vartheta\)-function
Cited In (32)
- Computational study of a branching algorithm for the maximum \(k\)-cut problem
- A framework for solving mixed-integer semidefinite programs
- Engineering branch-and-cut algorithms for the equicut problem
- An Efficient Semidefinite Programming Relaxation for the Graph Partition Problem
- Semidefinite relaxations for partitioning, assignment and ordering problems
- Semidefinite relaxations for partitioning, assignment and ordering problems
- Conic approximation to quadratic optimization with linear complementarity constraints
- An iterative scheme for valid polynomial inequality generation in binary polynomial programming
- SDP-based bounds for graph partition via extended ADMM
- A two-level graph partitioning problem arising in mobile wireless communications
- New bounds for the \(\max\)-\(k\)-cut and chromatic number of a graph
- A branch‐and‐price approach to k‐clustering minimum biclique completion problem
- Robust critical node selection by Benders decomposition
- A branch-and-bound algorithm for solving max-\(k\)-cut problem
- SOS-SDP: An Exact Solver for Minimum Sum-of-Squares Clustering
- Projection results for the \(k\)-partition problem
- A computational study for bilevel quadratic programs using semidefinite relaxations
- An extended edge-representative formulation for the \(K\)-partitioning problem
- Improving the linear relaxation of maximum \(k\)-cut with semidefinite-based constraints
- Computational study of valid inequalities for the maximum \(k\)-cut problem
- Orbitopal fixing
- Computational Approaches to Max-Cut
- Exploiting sparsity for the min \(k\)-partition problem
- On semidefinite programming relaxations of maximum \(k\)-section
- New formulations for the conflict resolution problem in the scheduling of television commercials
- Combining clustered adaptive multistart and discrete dynamic convexized method for the max-cut problem
- A Fixed Parameter Algorithm for the Minimum Number Convex Partition Problem
- Polynomial optimization: tightening RLT-based branch-and-bound schemes with conic constraints
- SDP Relaxations for Some Combinatorial Optimization Problems
- A semidefinite relaxation based global algorithm for two-level graph partition problem
- A multiple search operator heuristic for the max-k-cut problem
- Solving \(k\)-cluster problems to optimality with semidefinite programming
Uses Software
This page was built for publication: A branch-and-cut algorithm based on semidefinite programming for the minimum \(k\)-partition problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q646707)
