Approximation algorithm for MAX DICUT with given sizes of parts

DOI10.1007/S10255-003-0104-4zbMATH Open1138.90495OpenAlexW2001299319MaRDI QIDQ1879136FDOQ1879136

Guanghui Liu, Dachuan 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) Combinatorial optimization (90C27) Semidefinite programming (90C22) Boolean programming (90C09)

Cites Work

• Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones
• Optimization, approximation, and complexity classes
• Approximation algorithms for maximization problems arising in graph partitioning
• Semidefinite relaxation and nonconvex quadratic optimization
• Improved approximation algorithms for MAX \(k\)-CUT and MAX BISECTION
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Approximation of dense-\(n/2\)-subgraph and the complement of min-bisection
• Title not available (Why is that?)
• A .699-approximation algorithm for Max-Bisection.
• An improved rounding method and semidefinite programming relaxation for graph partition
• Outward rotations: a tool for rounding solutions of semidefinite programming relaxations, with applications to max cut and other problems
• On approximation of max-vertex-cover
• Title not available (Why is that?)
• Semidefinite programming and combinatorial optimization
• A 0. 5-approximation algorithm for MAX DICUT with given sizes of parts

Cited In (4)

• A 0. 5-approximation algorithm for MAX DICUT with given sizes of parts
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

Uses Software

• SeDuMi
• Outward rotations

   Recommendations

• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• A 0. 5-approximation algorithm for MAX DICUT with given sizes of parts 👍 👎
• Improved approximation algorithms for MAX \(k\)-CUT and MAX BISECTION 👍 👎
• Title not available (Why is that?) 👍 👎

This page was built for publication: Approximation algorithm for MAX DICUT with given sizes of parts

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1879136)