Lagrangian smoothing heuristics for Max-cut
From MaRDI portal
Publication:2491324
DOI10.1007/s10732-005-3603-zzbMath1122.90426MaRDI QIDQ2491324
Publication date: 29 May 2006
Published in: Journal of Heuristics (Search for Journal in Brave)
Full work available at URL: http://edoc.hu-berlin.de/18452/3271
quadratic programming; semidefinite programming; combinatorial optimization; non-convex programming; pathfollowing; approximation methods and heuristics
90C22: Semidefinite programming
90C26: Nonconvex programming, global optimization
90C20: Quadratic programming
90C59: Approximation methods and heuristics in mathematical programming
90C27: Combinatorial optimization
Related Items
A filled function method for quadratic programs with binary constraints†, A new discrete filled function method for solving large scale max-cut problems, An efficient Lagrangian smoothing heuristic for max-cut, Global optimality conditions and optimization methods for quadratic integer programming problems, A discrete filled function algorithm for approximate global solutions of max-cut problems
Uses Software
Cites Work
- Proximity control in bundle methods for convex nondifferentiable minimization
- A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization
- Rank-Two Relaxation Heuristics for MAX-CUT and Other Binary Quadratic Programs
- Outward rotations
- 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
- Dual Applications of Proximal Bundle Methods, Including Lagrangian Relaxation of Nonconvex Problems
- Pathfollowing methods in nonlinear optimization III: Lagrange multiplier embedding
- Solving Large-Scale Sparse Semidefinite Programs for Combinatorial Optimization
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item