An efficient Lagrangian smoothing heuristic for max-cut

DOI10.1007/S13226-010-0039-4zbMATH Open1227.90033OpenAlexW2048237536MaRDI QIDQ549567FDOQ549567

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

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

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)

Cites Work

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

Cited In (3)

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

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)