A discrete dynamic convexized method for the max-cut problem

DOI10.1007/S10479-012-1133-2MaRDI QIDQ1761827zbMATH OpenOpenAlexFDO

Authors Geng Lin, Wenxing 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)

Recommendations

• A discrete filled function algorithm for approximate global solutions of max-cut problems
• Combining clustered adaptive multistart and discrete dynamic convexized method for the max-cut problem
• A new discrete filled function method for solving large scale max-cut problems
• A discrete filled function algorithm embedded with continuous approximation for solving max-cut problems
• scientific article; zbMATH DE number 5232308
• A continuation algorithm for max-cut problem
• A novel formulation of the max-cut problem and related algorithm
• A tight semidefinite relaxation of the MAX CUT problem
• Near-optimal approximation algorithm for simultaneous Max-Cut
• Cutting plane algorithm for convex generalized disjunctive programs

Cites work

• scientific article; zbMATH DE number 5232308 (Why is no real title available?)
• A Spectral Bundle Method for Semidefinite Programming
• A continuation algorithm for max-cut problem
• A discrete dynamic convexized method for nonlinear integer programming
• A discrete filled function algorithm embedded with continuous approximation for solving max-cut problems
• A discrete filled function algorithm for approximate global solutions of max-cut problems
• A projected gradient algorithm for solving the maxcut SDP relaxation
• An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
• An improved rounding method and semidefinite programming relaxation for graph partition
• Discrete dynamic convexized method for nonlinearly constrained nonlinear integer programming
• Feasible direction algorithm for solving the SDP relaxations of quadratic {−1, 1} programming problems
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Lagrangian smoothing heuristics for Max-cut
• Mixed linear and semidefinite programming for combinatorial and quadratic optimization
• P-Complete Approximation Problems
• Randomized heuristics for the Max-Cut problem
• Rank-two relaxation heuristics for MAX-CUT and other binary quadratic programs
• Some simplified NP-complete graph problems

Cited in

(14)

• A new discrete filled function method for solving large scale max-cut problems
• A discrete filled function algorithm for approximate global solutions of max-cut problems
• Dijkstra's algorithm and L-concave function maximization
• Computational approaches to MAX-cut
• An effective iterated tabu search for the maximum bisection problem
• Combining clustered adaptive multistart and discrete dynamic convexized method for the max-cut problem
• An effective discrete dynamic convexized method for solving the winner determination problem
• A gradient-based randomised heuristic for the maximum cut problem
• A multiple search operator heuristic for the max-k-cut problem
• Graph partitioning: an updated survey
• A cutting method for finding discrete minimax with dropping of cutting planes
• Solving the maxcut problem by the global equilibrium search
• A discrete dynamic convexized method for VLSI circuit partitioning
• A max-cut approximation using a graph based MBO scheme

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1761827)