Solving Graph Bisection Problems with Semidefinite Programming

DOI10.1287/ijoc.12.3.177.12637zbMath1040.90045OpenAlexW2150683370MaRDI QIDQ4427330

Jens Clausen, Stefan E. Karisch, Franz Rendl

Publication date: 28 October 2003

Published in: INFORMS Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/682934d030294e90c3dd8a15c87a74ff061a228d

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Semidefinite programming (90C22)

Related Items

Exploiting low-rank structure in semidefinite programming by approximate operator splitting, A FULL NT-STEP INFEASIBLE INTERIOR-POINT ALGORITHM FOR SEMIDEFINITE OPTIMIZATION BASED ON A SELF-REGULAR PROXIMITY, An effective iterated tabu search for the maximum bisection problem, An exact algorithm for min-max hyperstructure equipartition with a connected constraint, Memetic search for the max-bisection problem, A nonmonotone GRASP, Graph bisection revisited, On the bridge between combinatorial optimization and nonlinear optimization: a family of semidefinite bounds for 0--1 quadratic problems leading to quasi-Newton methods, A branch-and-bound algorithm for the minimum cut linear arrangement problem, ILP-Based Local Search for Graph Partitioning, Partitioning through projections: strong SDP bounds for large graph partition problems, Simplified infeasible interior-point algorithm for SDO using full Nesterov-Todd step, An exact algorithm for graph partitioning, An Efficient Semidefinite Programming Relaxation for the Graph Partition Problem, Semidefinite programming relaxations for the graph partitioning problem, Quadratic convex reformulations for quadratic 0-1 programming, A projected gradient algorithm for solving the maxcut SDP relaxation, Exploiting semidefinite relaxations in constraint programming, Finding optimal solutions to the graph partitioning problem with heuristic search, A new full-Newton step \(O(n)\) infeasible interior-point algorithm for semidefinite optimization, An exact combinatorial algorithm for minimum graph bisection, Improving the performance of standard solvers for quadratic 0-1 programs by a tight convex reformulation: The QCR method, Advanced Coarsening Schemes for Graph Partitioning, Unnamed Item, Engineering Branch-and-Cut Algorithms for the Equicut Problem, Mixed linear and semidefinite programming for combinatorial and quadratic optimization, Semidefinite programming and eigenvalue bounds for the graph partition problem