A General Regularized Continuous Formulation for the Maximum Clique Problem

• 成果类型: Article
• 署名作者: Hungerford, James T.; Rinaldi, Francesco
• 署名单位: University of Padua
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2018.0954
• 发表日期: 2019
• 页码: 1161-1173
• 关键词: optimality conditions

摘要

In this paper, we develop a general regularization-based continuous optimization framework for the maximum clique problem. In particular, we consider a broad class of regularization terms that can be included in the classic Motzkin-Straus formulation, and we develop conditions that guarantee the equivalence between the continuous regularized problem and the original one in both a global and a local sense. We further analyze, from a computational point of view, two different regularizers that satisfy the general conditions.