A new trust region technique for the maximum weight clique problem A new simple generalization of the Motzkin-Straus theorem for the maximum weight clique problem is formulated and directly proved. Within this framework a trust region heuristic is developed. In contrast to usual trust region methods, it regards not only the global optimum of a quadratic objective over a sphere, but also a set of other stationary points of the program. We formulate and prove a condition when a Motzkin-Straus optimum coincides with such a point. The developed method has complexity O(n 3 ), where n is the number of vertices of the graph. It was implemented in a publicly available software package QUALEX-MS. Computational experiments indicate that the algorithm is exact on small graphs and very efficient on the DIMACS benchmark graphs and various random maximum weight clique problem instances

References in zbMATH (referenced in 39 articles )

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

1 2 next

  1. Chang, Yanming; Peng, Yuejian; Yao, Yuping: Connection between a class of polynomial optimization problems and maximum cliques of non-uniform hypergraphs (2016)
  2. Gu, Ran; Li, Xueliang; Peng, Yuejian; Shi, Yongtang: Some Motzkin-Straus type results for non-uniform hypergraphs (2016)
  3. Hazan, Elad; Koren, Tomer: A linear-time algorithm for trust region problems (2016)
  4. Wang, Yang; Hao, Jin-Kao; Glover, Fred; Lü, Zhipeng; Wu, Qinghua: Solving the maximum vertex weight clique problem via binary quadratic programming (2016)
  5. Peng, Yuejian; Tang, Qingsong; Zhao, Cheng: On Lagrangians of $r$-uniform hypergraphs (2015)
  6. Wu, Qinghua; Hao, Jin-Kao: A review on algorithms for maximum clique problems (2015)
  7. Sun, Yanping; Tang, Qingsong; Zhao, Cheng; Peng, Yuejian: On the largest graph-Lagrangian of 3-graphs with fixed number of edges (2014)
  8. Tang, Qingsong; Peng, Yuejian; Zhang, Xiangde; Zhao, Cheng: On graph-Lagrangians of hypergraphs containing dense subgraphs (2014)
  9. Gruzdeva, Tatyana V.: On a continuous approach for the maximum weighted clique problem (2013)
  10. Peng, Yuejian; Zhao, Cheng: A Motzkin-Straus type result for 3-uniform hypergraphs (2013)
  11. Pištěk, Miroslav: Approximate dynamic programming based on high dimensional model representation (2013)
  12. Smith, Derek H.; Montemanni, Roberto: Permutation codes with specified packing radius (2013)
  13. Wu, Qinghua; Hao, Jin-Kao: An adaptive multistart tabu search approach to solve the maximum clique problem (2013)
  14. Gualandi, Stefano; Malucelli, Federico: Exact solution of graph coloring problems via constraint programming and column generation (2012)
  15. Held, Stephan; Cook, William; Sewell, Edward C.: Maximum-weight stable sets and safe lower bounds for graph coloring (2012)
  16. McClosky, Benjamin; Hicks, Illya V.: Combinatorial algorithms for the maximum $k$-plex problem (2012)
  17. Rebennack, Steffen; Reinelt, Gerhard; Pardalos, Panos M.: A tutorial on branch and cut algorithms for the maximum stable set problem (2012)
  18. Wu, Qinghua; Hao, Jin-Kao; Glover, Fred: Multi-neighborhood tabu search for the maximum weight clique problem (2012)
  19. Cai, Shaowei; Su, Kaile; Sattar, Abdul: Local search with edge weighting and configuration checking heuristics for minimum vertex cover (2011)
  20. Pullan, Wayne; Mascia, Franco; Brunato, Mauro: Cooperating local search for the maximum clique problem (2011)

1 2 next