QUALEX
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
Keywords for this software
References in zbMATH (referenced in 51 articles )
Showing results 1 to 20 of 51.
Sorted by year (- Letchford, Adam N.; Rossi, Fabrizio; Smriglio, Stefano: The stable set problem: clique and nodal inequalities revisited (2020)
- Wang, Yiyuan; Cai, Shaowei; Chen, Jiejiang; Yin, Minghao: SCCWalk: an efficient local search algorithm and its improvements for maximum weight clique problem (2020)
- Tang, Qingsong; Zhang, Xiangde; Zhao, Cheng: On cliques and Lagrangians of hypergraphs (2019)
- Chang, Yan-Ming; Peng, Yue-Jian: Maximum cliques of hypergraphs and polynomial optimization (2018)
- Hosseinian, Seyedmohammadhossein; Fontes, Dalila B. M. M.; Butenko, Sergiy: A nonconvex quadratic optimization approach to the maximum edge weight clique problem (2018)
- Levi, Amit; Yoshida, Yuichi: Sublinear-time quadratic minimization via spectral decomposition of matrices (2018)
- Tang, Qingsong; Zhang, Xiangde; Wang, Guoren; Zhao, Cheng: A continuous characterization of the maximum vertex-weighted clique in hypergraphs (2018)
- Tang, Qingsong; Peng, Yuejian; Zhang, Xiangde; Zhao, Cheng: On Motzkin-Straus type results for non-uniform hypergraphs (2017)
- Zhou, Yi; Hao, Jin-Kao; Goëffon, Adrien: PUSH: A generalized operator for the maximum vertex weight clique problem (2017)
- Botella, Arnaud; Lévy, Bruno; Caumon, Guillaume: Indirect unstructured hex-dominant mesh generation using tetrahedra recombination (2016)
- Chang, Yanming; Peng, Yuejian; Yao, Yuping: Connection between a class of polynomial optimization problems and maximum cliques of non-uniform hypergraphs (2016)
- Gu, Ran; Li, Xueliang; Peng, Yuejian; Shi, Yongtang: Some Motzkin-Straus type results for non-uniform hypergraphs (2016)
- Hazan, Elad; Koren, Tomer: A linear-time algorithm for trust region problems (2016)
- Wang, Yang; Hao, Jin-Kao; Glover, Fred; Lü, Zhipeng; Wu, Qinghua: Solving the maximum vertex weight clique problem via binary quadratic programming (2016)
- Bhattacharyya, Malay; Bandyopadhyay, Sanghamitra: Finding quasi core with simulated stacked neural networks (2015)
- Peng, Yuejian; Tang, Qingsong; Zhao, Cheng: On Lagrangians of (r)-uniform hypergraphs (2015)
- Wu, Qinghua; Hao, Jin-Kao: A review on algorithms for maximum clique problems (2015)
- Sun, Yanping; Tang, Qingsong; Zhao, Cheng; Peng, Yuejian: On the largest graph-Lagrangian of 3-graphs with fixed number of edges (2014)
- Tang, Qingsong; Peng, Yuejian; Zhang, Xiangde; Zhao, Cheng: On graph-Lagrangians of hypergraphs containing dense subgraphs (2014)
- Gruzdeva, Tatyana V.: On a continuous approach for the maximum weighted clique problem (2013)