A discrete filled function algorithm for approximate global solutions of max-cut problems

DOI10.1016/j.cam.2007.09.012zbMath1148.65041MaRDI QIDQ939569

Ai-Fan Ling, Cheng-Xian Xu, Feng-Min Xu

Publication date: 22 August 2008

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

Full work available at URL: https://doi.org/10.1016/j.cam.2007.09.012

zbMATH Keywords

global optimization; combinatorial optimization; max-cut problem; filled function; neighborhood local search

Mathematics Subject Classification ID

65K05: Numerical mathematical programming methods

90C20: Quadratic programming

90C27: Combinatorial optimization

Related Items

A continuously differentiable filled function method for global optimization, Combining clustered adaptive multistart and discrete dynamic convexized method for the max-cut problem, A discrete dynamic convexized method for the max-cut problem

Uses Software

• CirCut
• Outward rotations

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A filled function method for finding a global minimizer on global integer optimization
• A filled function method for finding a global minimizer of a function of several variables
• Some simplified NP-complete graph problems
• A continuous approach to nonlinear integer programming
• Discrete filled function method for discrete global optimization
• A new filled function method for nonlinear integer programming problem
• Lagrangian smoothing heuristics for Max-cut
• A projected gradient algorithm for solving the maxcut SDP relaxation
• Rank-Two Relaxation Heuristics for MAX-CUT and Other Binary Quadratic Programs
• Outward rotations
• An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Randomized heuristics for the Max-Cut problem
• An approximate algorithm for nonlinear integer programming
• A new filled function method for global optimization
• Finding global minima with a computable filled function.
• Filled functions for unconstrained global optimization.