An efficient Lagrangian smoothing heuristic for max-cut

DOI10.1007/s13226-010-0039-4zbMath1227.90033OpenAlexW2048237536MaRDI QIDQ549567

Zi Xu, Yong Xia

Publication date: 18 July 2011

Published in: Indian Journal of Pure \& Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s13226-010-0039-4

zbMATH Keywords

Lagrangian smoothingheuristicFrank-Wolfe algorithmmax-cut

Mathematics Subject Classification ID

Derivative-free methods and methods using generalized derivatives (90C56) Optimality conditions and duality in mathematical programming (90C46) Combinatorial optimization (90C27)

Uses Software

• CirCut

Cites Work

• Unnamed Item
• New optimality conditions for quadratic optimization problems with binary constraints
• Lagrangian smoothing heuristics for Max-cut
• Global Optimality Conditions for Quadratic Optimization Problems with Binary Constraints
• Rank-Two Relaxation Heuristics for MAX-CUT and Other Binary Quadratic Programs
• An exact penalty approach for solving a class of minimization problems with boolean variables
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Randomized heuristics for the Max-Cut problem
• A Spectral Bundle Method for Semidefinite Programming

This page was built for publication: An efficient Lagrangian smoothing heuristic for max-cut