A discrete filled function algorithm for approximate global solutions of max-cut problems
type: Item
instance of: scholarly article
title: A discrete filled function algorithm for approximate global solutions of max-cut problems
zbMATH Open document ID: 1148.65041
author: Ai-Fan Ling
author: Cheng-Xian Xu
author: Feng-Min Xu
published in: Journal of Computational and Applied Mathematics
publication date: 2008-08-22T00:00:00Z
review text: There have been very few attempts in using the filled function methods to solve max-cut or other combinatorial optimization problem. The max-cut problem can be expressed as a discrete quadratic optimization problem. This paper proposes a discrete filled function algorithm to find approximate global solutions for NP-hard max-cut problems. The proposed algorithm is implemented by a two-phase cycle. In the first phase, a local minimizer is obtained by using the 1-neighborhood local search in the objective function of the discrete quadratic optimization problem. In the second phase, the discrete filled function from some neighbor points of the local optimizer is minimized. The two cycles are iterated until the stopping conditions are met. Some numerical experimental results are presented.
Mathematics Subject Classification ID: 65K05
Mathematics Subject Classification ID: 90C20
Mathematics Subject Classification ID: 90C27
zbMATH DE Number: 5315426
zbMATH Keywords: combinatorial optimization
zbMATH Keywords: global optimization
zbMATH Keywords: filled function
zbMATH Keywords: max-cut problem
zbMATH Keywords: neighborhood local search
describes a project that uses: Outward rotations
describes a project that uses: CirCut
MaRDI profile type: Publication
full work available at URL: j.cam.2007.09.012
OpenAlex ID: W1965219960
cites work: Lagrangian smoothing heuristics for Max-cut
cites work: An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
cites work: Q4247459
cites work: A projected gradient algorithm for solving the maxcut SDP relaxation
cites work: Rank-two relaxation heuristics for MAX-CUT and other binary quadratic programs
cites work: Randomized heuristics for the Max-Cut problem
cites work: Some simplified NP-complete graph problems
cites work: A filled function method for finding a global minimizer of a function of several variables
cites work: A continuous approach to nonlinear integer programming
cites work: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
cites work: A new filled function method for nonlinear integer programming problem
cites work: Q4142699
cites work: Finding global minima with a computable filled function.
cites work: Discrete filled function method for discrete global optimization
cites work: A filled function method for finding a global minimizer on global integer optimization
cites work: Q5440597
cites work: Q5716604
cites work: Filled functions for unconstrained global optimization.
cites work: A new filled function method for global optimization
cites work: An approximate algorithm for nonlinear integer programming
cites work: Outward rotations: a tool for rounding solutions of semidefinite programming relaxations, with applications to max cut and other problems
DOI: 10.1016/J.CAM.2007.09.012
description: scientific article; zbMATH DE number 5315426