Rank-two relaxation heuristics for MAX-CUT and other binary quadratic programs The Goemans--Williamson randomized algorithm guarantees a high-quality approximation to the MAX-CUT problem, but the cost associated with such an approximation can be excessively high for large-scale problems due to the need for solving an expensive semidefinite relaxation. In order to achieve better practical performance, we propose an alternative, rank-two relaxation and develop a specialized version of the Goemans--Williamson technique. The proposed approach leads to continuous optimization heuristics applicable to MAX-CUT as well as other binary quadratic programs, for example the MAX-BISECTION problem.par A computer code based on the rank-two relaxation heuristics is compared with two state-of-the-art semidefinite programming codes that implement the Goemans--Williamson randomized algorithm, as well as with a purely heuristic code for effectively solving a particular MAX-CUT problem arising in physics. Computational results show that the proposed approach is fast and scalable and, more importantly, attains a higher approximation quality in practice than that of the Goemans--Williamson randomized algorithm. An extension to MAX-BISECTION is also discussed, as is an important difference between the proposed approach and the Goemans--Williamson algorithm; namely, that the new approach does not guarantee an upper bound on the MAX-CUT optimal value.

References in zbMATH (referenced in 35 articles , 1 standard article )

Showing results 1 to 20 of 35.
Sorted by year (citations)

1 2 next

  1. Mu, Xuewen; Liu, Wenlong: An augmented Lagrangian method for binary quadratic programming based on a class of continuous functions (2016)
  2. Shylo, V.P.; Glover, F.; Sergienko, I.V.: Teams of global equilibrium search algorithms for solving the weighted maximum cut problem in parallel (2015)
  3. Lin, Geng; Zhu, Wenxing: Combining clustered adaptive multistart and discrete dynamic convexized method for the max-cut problem (2014)
  4. Chen, Jein-Shan; Li, Jing-Fan; Wu, Jia: A continuation approach for solving binary quadratic program based on a class of NCP-functions (2012)
  5. Ling, Ai-fan; Xu, Cheng-xian: A new discrete filled function method for solving large scale max-cut problems (2012)
  6. Shylo, V.P.; Shylo, O.V.; Roschyn, V.À.: Solving weighted max-cut problem by global equilibrium search (2012)
  7. Wang, Yang; Lü, Zhipeng; Glover, Fred; Hao, Jin-Kao: Path relinking for unconstrained binary quadratic programming (2012)
  8. Wu, Z.Y.; Li, G.Q.; Quan, J.: Global optimality conditions and optimization methods for quadratic integer programming problems (2011)
  9. Fan, Neng; Pardalos, Panos M.: Linear and quadratic programming approaches for the general graph partitioning problem (2010)
  10. Kisialiou, Mikalai; Luo, Zhi-Quan: Probabilistic analysis of semidefinite relaxation for binary quadratic minimization (2010)
  11. Rendl, Franz; Rinaldi, Giovanni; Wiegele, Angelika: Solving Max-cut to optimality by intersecting semidefinite and polyhedral relaxations (2010)
  12. Shylo, V.P.; Shylo, O.V.: Solving the maxcut problem by the global equilibrium search (2010)
  13. Xia, Yong; Xu, Zi: An efficient Lagrangian smoothing heuristic for max-cut (2010)
  14. Laguna, Manuel; Duarte, Abraham; Martí, Rafael: Hybridizing the cross-entropy method: An application to the max-cut problem (2009)
  15. Ling, Ai-Fan; Xu, Cheng-Xian; Xu, Feng-Min: A discrete filled function algorithm embedded with continuous approximation for solving max-cut problems (2009)
  16. Boros, Endre; Hammer, Peter L.; Sun, Richard; Tavares, Gabriel: A Max-flow approach to improved lower bounds for quadratic unconstrained binary optimization (QUBO) (2008)
  17. Ling, Ai-Fan; Xu, Cheng-Xian; Xu, Feng-Min: A discrete filled function algorithm for approximate global solutions of max-cut problems (2008)
  18. Pan, Shaohua; Tan, Tao; Jiang, Yuxi: A global continuation algorithm for solving binary quadratic programming problems (2008)
  19. Śliwa, I.; Grygiel, K.; Szlachetka, P.: Hyperchaotic beats and their collapse to the quasiperiodic oscillations (2008)
  20. Burer, Samuel; Lee, Jon: Solving maximum-entropy sampling problems using factored masks (2007)

1 2 next