A .699-approximation algorithm for Max-Bisection.
From MaRDI portal
Publication:5930726
DOI10.1007/s101070100213zbMath1059.90119MaRDI QIDQ5930726
Publication date: 1 November 2001
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Semidefinite programming (90C22) Combinatorial optimization (90C27) Approximation algorithms (68W25) Discrete approximations in optimal control (49M25)
Related Items
Improved approximating \(2\)-CatSP for \(\sigma\geq 0.50\) with an unbalanced rounding matrix, An improved approximation algorithm for the \(2\)-catalog segmentation problem using semidefinite programming relaxation, Improved approximations for max set splitting and max NAE SAT, Approximation algorithm for MAX DICUT with given sizes of parts, Semidefinite relaxation for two mixed binary quadratically constrained quadratic programs: algorithms and approximation bounds, Complexity of approximating CSP with balance/hard constraints, Memetic search for the max-bisection problem, An approximation algorithm for the balanced Max-3-Uncut problem using complex semidefinite programming rounding, On semidefinite programming relaxations of maximum \(k\)-section, A maximum hypergraph 3-cut problem with limited unbalance: approximation and analysis, An approximation algorithm for scheduling two parallel machines with capacity constraints., Primal-dual optimization algorithms over Riemannian manifolds: an iteration complexity analysis, Improved approximation algorithms for the max-bisection and the disjoint 2-catalog segmentation problems, The capacitated max \(k\)-cut problem, A successive quadratic programming algorithm for SDP relaxation of Max-Bisection, Approximation algorithms for maximum cut with limited unbalance, Global Cardinality Constraints Make Approximating Some Max-2-CSPs Harder, A modified VNS metaheuristic for max-bisection problems, An improved kernel for max-bisection above tight lower bound, A new Lagrangian net algorithm for solving max-bisection problems, A multiple penalty function method for solving max-bisection problems, Approximation algorithms for MAX RES CUT with limited unbalanced constraints, An SDP randomized approximation algorithm for max hypergraph cut with limited unbalance, Computational experience with a SDP-based algorithm for maximum cut with limited unbalance, Relaxations of Combinatorial Problems Via Association Schemes, A proximal augmented method for semidefinite programming problems, Semidefinite approximation bound for a class of nonhomogeneous nonconvex quadratically constrained quadratic programming problem, On approximation of max-vertex-cover, Approximating Max Cut with Limited Unbalance, Speeding up a memetic algorithm for the max-bisection problem, Improved approximation algorithms for maximum graph partitioning problems, An improved semidefinite programming hierarchies rounding approximation algorithm for maximum graph bisection problems
