A discrete dynamic convexized method for the max-cut problem

DOI10.1007/s10479-012-1133-2zbMath1269.90130OpenAlexW2023809267MaRDI QIDQ1761827

Geng Lin, Wen-Xing Zhu

Publication date: 15 November 2012

Published in: Annals of Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10479-012-1133-2

zbMATH Keywords

local searchmax-cut problemdynamic convexized method

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59)

Related Items (5)

An effective discrete dynamic convexized method for solving the winner determination problem ⋮ An effective iterated tabu search for the maximum bisection problem ⋮ Graph partitioning: an updated survey ⋮ Combining clustered adaptive multistart and discrete dynamic convexized method for the max-cut problem ⋮ A multiple search operator heuristic for the max-k-cut problem

Cites Work

• Unnamed Item
• A discrete filled function algorithm for approximate global solutions of max-cut problems
• A discrete dynamic convexized method for nonlinear integer programming
• A discrete filled function algorithm embedded with continuous approximation for solving max-cut problems
• Discrete dynamic convexized method for nonlinearly constrained nonlinear integer programming
• Some simplified NP-complete graph problems
• An improved rounding method and semidefinite programming relaxation for graph partition
• Lagrangian smoothing heuristics for Max-cut
• A continuation algorithm for max-cut problem
• A projected gradient algorithm for solving the maxcut SDP relaxation
• Rank-Two Relaxation Heuristics for MAX-CUT and Other Binary Quadratic Programs
• Feasible direction algorithm for solving the SDP relaxations of quadratic {−1, 1} programming problems
• An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
• P-Complete Approximation Problems
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Randomized heuristics for the Max-Cut problem
• Mixed linear and semidefinite programming for combinatorial and quadratic optimization
• A Spectral Bundle Method for Semidefinite Programming

This page was built for publication: A discrete dynamic convexized method for the max-cut problem