Abstract
A new algorithm based on the global equilibrium search (GES) is developed to solve the weighted max-cut problem and is compared with currently the best solution algorithms. The advantages of the GES algorithm both in the performance and in the possibility of finding the best solutions are shown.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
S. Poljak and Z. Tuza, “Maximum cuts and large bipartite subgraphs,” DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 20, 181–244 (1995).
S. Burer, R. D. C. Monteiro, and Y. Zhang, “Rank-two relaxation heuristics for MAX-CUT and other binary quadratic programs,” SIAM J. on Optimization, 12, 503–521 (2002).
P. Festa, P. M. Pardalos, M. G. C. Resende, and C.C. Ribeiro, “Randomized heuristics for the maxcut problem,” Optimization Methods and Software, 17, 1033–1058 (2002).
M. X. Goemans and D. P. Williamson, “Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming,” J. of ACM, 42, 1115–1145 (1995).
G. Palubeckis and V. Krivickiene, “Application of multistart tabu search to the MAX-CUT problem,” in: Information Technology and Control, 2(31), Technologija, Kaunas (2004), pp. 29–35.
R. Marti, A. Duarte, and M. Laguna, “Advanced scatter search for the MAX-CUT problem,” INFORMS J. on Computing, 21, No. 1, 26–38 (2009).
V. P. Shilo, “The method of global equilibrium search,” Cybern. Syst. Analysis, 35, No. 1, 68–73 (1999).
I. V. Sergienko and V. P. Shylo, Discrete Optimization Problems: Challenges, Methods of Solution, and Analysis [in Russian], Naukova Dumka, Kyiv (2003).
V. P. Shylo and O. V. Shylo, “Solving the maxcut problem by the global equilibrium search,” Cybern. Syst. Analysis, 46, No. 5, 744–754 (2010).
V. P. Shylo and O. V. Shylo, “Path relinking scheme for the MAX-CUT problem within global equilibrium search,” Intern. J. of Swarm Intelligence Research (IJSIR), 2, No. 2, 42–51 (2011).
P. Pardalos, O. Prokopyev, O. Shylo, and V. Shylo, “Global equilibrium search applied to the unconstrained binary quadratic optimization problem,” Optimization Methods and Software, 23, 129–140 (2008).
V. P. Shylo and O. V. Shylo, “Solving unconstrained binary quadratic programming problem by global equilibrium search,” Cybern. Syst. Analysis, 47, No. 6, 889–897 (2011).
S. Kirkpatrick, C. D. Gelatti, and M. P. Vecchi, “Optimization by simulated annealing,” Science, 220, 671–680 (1983).
C. Helmberg and F. Rendl, “A spectral bundle method for semidefinite programming,” SIAM J. on Optimization, 10, 673–696 (2000).
Author information
Authors and Affiliations
Corresponding author
Additional information
Translated from Kibernetika i Sistemnyi Analiz, No. 4, July–August, 2012, pp. 101–105.
Rights and permissions
About this article
Cite this article
Shylo, V.P., Shylo, O.V. & Roschyn, V.À. Solving weighted max-cut problem by global equilibrium search. Cybern Syst Anal 48, 563–567 (2012). https://doi.org/10.1007/s10559-012-9435-6
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10559-012-9435-6