Approximation algorithm for MAX DICUT with given sizes of parts

DOI10.1007/s10255-003-0104-4zbMath1138.90495OpenAlexW2001299319MaRDI QIDQ1879136

Guang-Hui Liu, Da-Chuan Xu

Publication date: 22 September 2004

Published in: Acta Mathematicae Applicatae Sinica. English Series (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10255-003-0104-4

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Semidefinite programming (90C22) Combinatorial optimization (90C27) Boolean programming (90C09)

Uses Software

• SeDuMi
• Outward rotations

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Optimization, approximation, and complexity classes
• Approximation of dense-\(n/2\)-subgraph and the complement of min-bisection
• On approximation of max-vertex-cover
• An improved rounding method and semidefinite programming relaxation for graph partition
• A 0.5-Approximation Algorithm for MAX DICUT with Given Sizes of Parts
• Approximation Algorithms for Maximization Problems Arising in Graph Partitioning
• Outward rotations
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Semidefinite relaxation and nonconvex quadratic optimization
• Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones
• Semidefinite programming and combinatorial optimization
• A .699-approximation algorithm for Max-Bisection.