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 39 articles , 1 standard article )

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

1 2 next

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

1 2 next