An efficient Lagrangian smoothing heuristic for max-cut

DOI10.1007/S13226-010-0039-4MaRDI QIDQ549567zbMATH OpenOpenAlexFDO

Authors Yong Xia, Zi Xu

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

heuristicFrank-Wolfe algorithmmax-cutLagrangian smoothing

Mathematics Subject Classification ID

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

Recommendations

• Lagrangian smoothing heuristics for Max-cut
• A continuation algorithm for max-cut problem
• A new Lagrangian net algorithm for solving max-bisection problems
• A CONTINUATION APPROACH USING NCP FUNCTION FOR SOLVING MAX-CUT PROBLEM
• A branch-and-bound algorithm for solving max-\(k\)-cut problem

Cites work

• scientific article; zbMATH DE number 1302192 (Why is no real title available?)
• A Spectral Bundle Method for Semidefinite Programming
• An exact penalty approach for solving a class of minimization problems with boolean variables
• Global optimality conditions for quadratic optimization problems with binary constraints
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Lagrangian smoothing heuristics for Max-cut
• New optimality conditions for quadratic optimization problems with binary constraints
• Randomized heuristics for the Max-Cut problem
• Rank-two relaxation heuristics for MAX-CUT and other binary quadratic programs

Cited in

(3)

• Lagrangian smoothing heuristics for Max-cut
• Smoothed complexity of local max-cut and binary max-CSP
• Smoothed Analysis of Local Search for the Maximum-Cut Problem

Describes a project that uses

Uses Software

• CirCut

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

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