RANDOMIZED HEURISTICS FOR THE MAX-CUT PROBLEM
作者： P. Festa , P.M. Pardalos , M.G.C. Resende , C.C. Ribeiro
DOI: 10.1080/1055678021000090033
关键词:
摘要: Given an undirected graph with edge weights, the MAX-CUT problem consists in finding a partition of nodes into two subsets, such that sum weights edges having endpoints different subsets is maximized. It well-known NP-hard applications several fields, including VLSI design and statistical physics. In this article, greedy randomized adaptive search procedure (GRASP), variable neighborhood (VNS), path-relinking (PR) intensification heuristic for are proposed tested. New hybrid heuristics combine GRASP, VNS, PR also Computational results indicate these find near-optimal solutions. On set standard test problems, new best known solutions were produced many instances.
core.ac.uk
optimization-online.org 
sci-hub.se 参考文章(37)
Fred Glover, Tabu Search and Adaptive Memory Programming — Advances, Applications and Challenges Operations Research/Computer Science Interfaces Series. pp. 1- 75 ,(1997) , 10.1007/978-1-4615-4102-8_1
Paola Festa, Mauricio G.C. Resende, Grasp: An Annotated Bibliography Springer, Boston, MA. pp. 325- 367 ,(2002) , 10.1007/978-1-4615-1507-4_15
Celso C Ribeiro, Pierre Hansen, Pierre Hansen, Nenad Mladenović, Developments of Variable Neighborhood Search Les Cahiers du GERAD. pp. 415- 439 ,(2002) , 10.1007/978-1-4615-1507-4_19
Katsuki Fujisawa, Mituhiro Fukuda, Masakazu Kojima, Kazuhide Nakata, Numerical Evaluation of SDPA (Semidefinite Programming Algorithm) Springer US. pp. 267- 301 ,(2000) , 10.1007/978-1-4757-3216-0_11
Fred Glover, Multi-Start and Strategic Oscillation Methods — Principles to Exploit Adaptive Memory Operations Research/Computer Science Interfaces Series. pp. 1- 23 ,(2000) , 10.1007/978-1-4615-4567-5_1
Ron Y. Pinter, Optimal layer assignment for interconnect Advances in VLSI and Computer Systems archive. ,vol. 1, pp. 123- 137 ,(1984) , 10.5555/2334.2335
Simone L Martins, Mauricio GC Resende, Celso C Ribeiro, Panos M Pardalos, A Parallel Grasp for the Steiner Tree Problem in Graphs Using a Hybrid Local Search Strategy Journal of Global Optimization. ,vol. 17, pp. 267- 283 ,(2000) , 10.1023/A:1026546708757
P. M. Pardalos, Mauricio G. C. Resende, Handbook of applied optimization Oxford University Press. ,(2002)
Steven J. Benson, Yinyu Yeb, Xiong Zhang, Mixed linear and semidefinite programming for combinatorial and quadratic optimization Optimization Methods & Software. ,vol. 11, pp. 515- 544 ,(1999) , 10.1080/10556789908805761
Richard M. Karp, Reducibility Among Combinatorial Problems Journal of Symbolic Logic. ,vol. 40, pp. 219- 241 ,(2010) , 10.1007/978-3-540-68279-0_8