A unified framework for obtaining improved approximation algorithms for maximum graph bisection problems
From MaRDI portal
Publication:4537628
DOI10.1002/RSA.10035zbMATH Open1017.68089OpenAlexW2019044741MaRDI QIDQ4537628FDOQ4537628
Authors: Eran Halperin, Uri Zwick 
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
Recommendations
- scientific article; zbMATH DE number 1762086
- Approximation algorithms for max cut and max bisection problems using semidefinite programming relaxations
- An improved semidefinite programming hierarchies rounding approximation algorithm for maximum graph bisection problems
- Improved approximation algorithms for MAX \(k\)-CUT and MAX BISECTION
- Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION
Cites Work
- The ellipsoid method and its consequences in combinatorial optimization
- Semidefinite relaxation and nonconvex quadratic optimization
- Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION
- On the cut polytope
- Derandomizing Approximation Algorithms Based on Semidefinite Programming
- Title not available (Why is that?)
- Outward rotations: a tool for rounding solutions of semidefinite programming relaxations, with applications to max cut and other problems
- Title not available (Why is that?)
- On the integrality ratio of semidefinite relaxations of MAX CUT
Cited In (38)
- Assortment planning for multiple chain stores
- Approximation with a fixed number of solutions of some multiobjective maximization problems
- Title not available (Why is that?)
- A 2-approximation for the maximum satisfying bisection problem
- FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
- Semidefinite relaxations for partitioning, assignment and ordering problems
- Semidefinite relaxations for partitioning, assignment and ordering problems
- An improved semidefinite programming hierarchies rounding approximation algorithm for maximum graph bisection problems
- An improved kernel for max-bisection above tight lower bound
- Improved approximation algorithms for maximum graph partitioning problems
- Better balance by being biased: a 0.8776-approximation for {\textsc{Max Bisection}}
- Simple probabilistic analysis to generalize bottleneck graph multi-partitioning
- Approximating Maximum Cut with Limited Unbalance
- An Enhancement of the Bisection Method Average Performance Preserving Minmax Optimality
- Global Cardinality Constraints Make Approximating Some Max-2-CSPs Harder
- An SDP randomized approximation algorithm for max hypergraph cut with limited unbalance
- On approximation of max \(\frac{n}{2}\)-uncut problem
- Speeding up a memetic algorithm for the max-bisection problem
- New semidefinite programming relaxations for the linear ordering and the traveling salesman problem
- 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
- Title not available (Why is that?)
- Improved approximation algorithms for MAX \(k\)-CUT and MAX BISECTION
- A multiple penalty function method for solving max-bisection problems
- A .699-approximation algorithm for Max-Bisection.
- Title not available (Why is that?)
- Memetic search for the max-bisection problem
- A new Lagrangian net algorithm for solving max-bisection problems
- On semidefinite programming relaxations of maximum \(k\)-section
- An approximation algorithm for the balanced Max-3-Uncut problem using complex semidefinite programming rounding
- A modified VNS metaheuristic for max-bisection problems
- A maximum hypergraph 3-cut problem with limited unbalance: approximation and analysis
- An Improved Semidefinite Programming Hierarchies Rounding Approximation Algorithm for Maximum Graph Bisection Problems
- Approximating CSPs with global cardinality constraints using SDP hierarchies
- Applications of the Dulmage--Mendelsohn Decomposition and Network Flow to Graph Bisection Improvement
- Improved approximation algorithms for the max-bisection and the disjoint 2-catalog segmentation problems
- Improved approximation algorithms for MAX \(\frac{n}2\)-DIRECTED-BISECTION and MAX \(\frac{n}2\)-DENSE-SUBGRAPH
- Bounds on the bisection width for random \(d\)-regular graphs
Uses Software
This page was built for publication: A unified framework for obtaining improved approximation algorithms for maximum graph bisection problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4537628)
