An approximation algorithm for the balanced Max-3-Uncut problem using complex semidefinite programming rounding
DOI10.1007/S10878-015-9880-ZzbMATH Open1356.90129OpenAlexW2002849997MaRDI QIDQ346478FDOQ346478
Chenchen Wu, Wen-Qing Xu, Dachuan Xu, Donglei Du
Publication date: 29 November 2016
Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10878-015-9880-z
Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Semidefinite programming (90C22)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- An explicit equivalent positive semidefinite program for nonlinear 0-1 programs
- Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION
- P-Complete Approximation Problems
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- One-Half Approximation Algorithms for the k-Partition Problem
- Better Balance by Being Biased: A 0.8776-Approximation for Max Bisection
- A .699-approximation algorithm for Max-Bisection.
- A unified framework for obtaining improved approximation algorithms for maximum graph bisection problems
- Improved approximation algorithms for MAX \(\frac{n}2\)-DIRECTED-BISECTION and MAX \(\frac{n}2\)-DENSE-SUBGRAPH
- An improved rounding method and semidefinite programming relaxation for graph partition
- Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming
- An improved semidefinite programming hierarchies rounding approximation algorithm for maximum graph bisection problems
- Outward rotations: a tool for rounding solutions of semidefinite programming relaxations, with applications to max cut and other problems
- An approximation algorithm for maxk-uncut with capacity constraints
- Approximation Algorithms for Max 3-Section Using Complex Semidefinite Programming Relaxation
- Complex Quadratic Optimization and Semidefinite Programming
- The RPR2 rounding technique for semidefinite programs
- Segmentation problems
Cited In (4)
- Computational experience with a SDP-based algorithm for maximum cut with limited unbalance
- Robust necessary optimality conditions for nondifferentiable complex fractional programming with uncertain data
- A Complex Semidefinite Programming Rounding Approximation Algorithm for the Balanced Max-3-Uncut Problem
- Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming
Uses Software
This page was built for publication: An approximation algorithm for the balanced Max-3-Uncut problem using complex semidefinite programming rounding
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q346478)
