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

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

1 2 3 next

  1. Chang, KungChing; Shao, SiHong; Zhang, Dong: Cheeger’s cut, maxcut and the spectral theory of 1-Laplacian on graphs (2017)
  2. Ma, Fuda; Hao, Jin-Kao: A multiple search operator heuristic for the max-k-cut problem (2017)
  3. Ma, Fuda; Hao, Jin-Kao; Wang, Yang: An effective iterated tabu search for the maximum bisection problem (2017)
  4. Boumal, Nicolas: Nonconvex phase synchronization (2016)
  5. De Santis, M.; Festa, P.; Liuzzi, G.; Lucidi, S.; Rinaldi, F.: A nonmonotone GRASP (2016)
  6. Mu, Xuewen; Liu, Wenlong: An augmented Lagrangian method for binary quadratic programming based on a class of continuous functions (2016)
  7. Shylo, V. P.; Glover, F.; Sergienko, I. V.: Teams of global equilibrium search algorithms for solving the weighted maximum cut problem in parallel (2015)
  8. Lin, Geng; Zhu, Wenxing: Combining clustered adaptive multistart and discrete dynamic convexized method for the max-cut problem (2014)
  9. Wang, Yang; Lü, Zhipeng; Glover, Fred; Hao, Jin-Kao: Probabilistic GRASP-tabu search algorithms for the UBQP problem (2013)
  10. Wu, Qinghua; Hao, Jin-Kao: Memetic search for the max-bisection problem (2013)
  11. Chen, Jein-Shan; Li, Jing-Fan; Wu, Jia: A continuation approach for solving binary quadratic program based on a class of NCP-functions (2012)
  12. Ling, Ai-fan; Xu, Cheng-xian: A new discrete filled function method for solving large scale max-cut problems (2012)
  13. Shylo, V. P.; Shylo, O. V.; Roschyn, V. À.: Solving weighted max-cut problem by global equilibrium search (2012) ioport
  14. Wang, Yang; Lü, Zhipeng; Glover, Fred; Hao, Jin-Kao: Path relinking for unconstrained binary quadratic programming (2012)
  15. Wu, Z. Y.; Li, G. Q.; Quan, J.: Global optimality conditions and optimization methods for quadratic integer programming problems (2011)
  16. Fan, Neng; Pardalos, Panos M.: Linear and quadratic programming approaches for the general graph partitioning problem (2010)
  17. Kisialiou, Mikalai; Luo, Zhi-Quan: Probabilistic analysis of semidefinite relaxation for binary quadratic minimization (2010)
  18. Rendl, Franz; Rinaldi, Giovanni; Wiegele, Angelika: Solving Max-cut to optimality by intersecting semidefinite and polyhedral relaxations (2010)
  19. Shylo, V. P.; Shylo, O. V.: Solving the maxcut problem by the global equilibrium search (2010)
  20. Xia, Yong; Xu, Zi: An efficient Lagrangian smoothing heuristic for max-cut (2010)

1 2 3 next