An approximation algorithm for the balanced Max-3-Uncut problem using complex semidefinite programming rounding

DOI10.1007/s10878-015-9880-zzbMath1356.90129OpenAlexW2002849997MaRDI QIDQ346478

Chen-Chen Wu, Wen-Qing Xu, Da-Chuan Xu, Dong-lei 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

zbMATH Keywords

approximation algorithmbalanced Max-3-Uncutcomplex semidefinite programming

Mathematics Subject Classification ID

Semidefinite programming (90C22) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Related Items

Robust necessary optimality conditions for nondifferentiable complex fractional programming with uncertain data

Uses Software

• Outward rotations

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION
• 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
• An Explicit Equivalent Positive Semidefinite Program for Nonlinear 0-1 Programs
• Outward rotations
• An approximation algorithm for maxk-uncut with capacity constraints
• Approximation Algorithms for Max 3-Section Using Complex Semidefinite Programming Relaxation
• One-Half Approximation Algorithms for the k-Partition Problem
• P-Complete Approximation Problems
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• A unified framework for obtaining improved approximation algorithms for maximum graph bisection problems
• Complex Quadratic Optimization and Semidefinite Programming
• The RPR2 rounding technique for semidefinite programs
• Segmentation problems
• Better Balance by Being Biased: A 0.8776-Approximation for Max Bisection
• A .699-approximation algorithm for Max-Bisection.

This page was built for publication: An approximation algorithm for the balanced Max-3-Uncut problem using complex semidefinite programming rounding