Approximation algorithms for MAX RES CUT with limited unbalanced constraints

DOI10.1007/s12190-009-0290-1zbMath1192.90234MaRDI QIDQ980434

Ai-Fan Ling, Cheng-Xian Xu, Le Tang

Publication date: 29 June 2010

Published in: Journal of Applied Mathematics and Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s12190-009-0290-1

zbMATH Keywords

semidefinite programming relaxation

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

90C06: Large-scale problems in mathematical programming

90C59: Approximation methods and heuristics in mathematical programming

90C27: Combinatorial optimization

Uses Software

• Outward rotations

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Improved approximation algorithms for maximum graph partitioning problems
• A discrete filled function algorithm embedded with continuous approximation for solving max-cut problems
• An improved rounding method and semidefinite programming relaxation for graph partition
• Approximation algorithms for maximum cut with limited unbalance
• 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
• Algorithms – ESA 2005
• The RPR2 rounding technique for semidefinite programs
• A .699-approximation algorithm for Max-Bisection.
• A survey of quasi-Newton equations and quasi-Newton methods for optimization