Solving the maxcut problem by the global equilibrium search

被引：12
作者：
Shylo V.P. [1 ]
Shylo O.V. [2 ]
机构：
[1] V. M. Glushkov Institute of Cybernetics, National Academy of Sciences of Ukraine, Kyiv
[2] University of Pittsburgh, Pittsburgh
来源：
Cybernetics and Systems Analysis | 2010年 / 46卷 / 05期
关键词：
algorithm efficiency; approximate methods; computational experiment; cutset; global equilibrium search;
D O I：
10.1007/s10559-010-9256-4
中图分类号：
学科分类号：
摘要：
The authors propose an approach to the solution of the maxcut problem. It is based on the global equilibrium search method, which is currently one of the most efficient discrete programming methods. The efficiency of the proposed algorithm is analyzed. © 2010 Springer Science+Business Media, Inc.
引用
收藏
页码：744 / 754
页数：10
相关论文
共 14 条
  • [1] Barahona F., Grotschel M., Junger M., Reinelt G., An application of combinatorial optimization to statistical physics and circuit layout design, Oper. Res., 36, pp. 493-513, (1988)
  • [2] Chang K.C., Dh-C D., Efficient algorithms for layer assignment problem, IEEE Trans. Computer-Aided Design of Integrated Circuits and Systems, 6, pp. 67-78, (1987)
  • [3] Poljak S., Tuza Z., Maximum cuts and large bipartite subgraphs, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 20, pp. 181-244, (1995)
  • [4] Shilo V.P., The method of global equilibrium search, Cybern. Syst. Analysis, 35, 1, pp. 68-74, (1999)
  • [5] Sergienko I.V., Shilo V.P., Discrete Optimization Problems: Challenges, Solution Methods, and Studies, (2003)
  • [6] Sergienko I.V., Shylo V.P., Problems of discrete optimization: Challenges and main approaches to solve them, Cybernetics and Systems Analysis, 42, 4, pp. 465-482, (2006)
  • [7] Pardalos P., Prokopyev O., Shylo O., Shylo V., Global equilibrium search applied to the unconstrained binary quadratic optimization problem, Optim. Methods and Software, 23, pp. 129-140, (2008)
  • [8] Prokopyev O., Shylo O., Shylo V., Solving weighted MAX-SAT via global equilibrium search, Oper. Res. Lett., 36, 4, pp. 434-438, (2008)
  • [9] Burer S., Monteiro R.D.C., Zhang Y., Rank-two relaxation heuristics for MAX-CUT and other binary quadratic programs, SIAM J. Optim., 12, pp. 503-521, (2002)
  • [10] Festa P., Pardalos P.M., Resende M.G.C., Ribeiro C.C., Randomized heuristics for the maxcut problem, Optim. Methods and Software, 17, pp. 1033-1058, (2002)
12