Approximation algorithm for MAX DICUT with given sizes of parts

DOI10.1007/S10255-003-0104-4MaRDI QIDQ1879136zbMATH OpenOpenAlexFDO

Authors Dachuan Xu, Guanghui Liu

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)

Recommendations

• scientific article; zbMATH DE number 1670527
• scientific article; zbMATH DE number 1670644
• A 0. 5-approximation algorithm for MAX DICUT with given sizes of parts
• Improved approximation algorithms for MAX \(k\)-CUT and MAX BISECTION
• scientific article; zbMATH DE number 1833408

Cites work

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

Cited in

(4)

• A 0. 5-approximation algorithm for MAX DICUT with given sizes of parts
• scientific article; zbMATH DE number 1670527 (Why is no real title available?)
• scientific article; zbMATH DE number 1304324 (Why is no real title available?)
• scientific article; zbMATH DE number 1833408 (Why is no real title available?)

Describes a project that uses

Uses Software

• Outward rotations
• SeDuMi

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)