A unified framework for obtaining improved approximation algorithms for maximum graph bisection problems

DOI10.1002/rsa.10035zbMath1017.68089OpenAlexW2019044741MaRDI QIDQ4537628

Uri Zwick, Eran Halperin

Publication date: 1 July 2002

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/rsa.10035

zbMATH Keywords

semidefinite programmingMAX CUT algorithm

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10)

Related Items (24)

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 ⋮ Bounds on the bisection width for random \(d\)-regular graphs ⋮ 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 ⋮ Approximation with a fixed number of solutions of some multiobjective maximization problems ⋮ A maximum hypergraph 3-cut problem with limited unbalance: approximation and analysis ⋮ Improved approximation algorithms for the max-bisection and the disjoint 2-catalog segmentation problems ⋮ 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 ⋮ An SDP randomized approximation algorithm for max hypergraph cut with limited unbalance ⋮ Simple probabilistic analysis to generalize bottleneck graph multi-partitioning ⋮ New semidefinite programming relaxations for the linear ordering and the traveling salesman problem ⋮ Semidefinite relaxations for partitioning, assignment and ordering problems ⋮ Semidefinite relaxations for partitioning, assignment and ordering problems ⋮ Assortment planning for multiple chain stores ⋮ Unnamed Item ⋮ 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

Uses Software

• Outward rotations

Cites Work

• Unnamed Item
• Unnamed Item
• Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION
• The ellipsoid method and its consequences in combinatorial optimization
• Outward rotations
• Derandomizing Approximation Algorithms Based on Semidefinite Programming
• Semidefinite relaxation and nonconvex quadratic optimization
• On the cut polytope
• On the integrality ratio of semidefinite relaxations of MAX CUT

This page was built for publication: A unified framework for obtaining improved approximation algorithms for maximum graph bisection problems