Scholarlink

In 1965, Motzkin and Straus established a profound connection between the clique number of a graph and the global maxima of a quadratic program defined on the standard simplex. Since then, a line of active and intensive research has been yielding heuristics and bounds concerning the maximum clique problem, thanks to the discoveries pertaining to local/global solutions of the Motzkin-Straus program. However, the Karush-Kuhn-Tucker (KKT) points thereof have received little to no attention in the literature. In this work, a parameterized version of the Motzkin-Straus program is discussed, and some results about its KKT points are obtained. What emerges is a connection between a generalized notion of KKT point and some regular structures contained in the graph.

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

On Generalized KKT Points of the Motzkin-Straus Program

  • 会议论文

  • 发表日期：

    2025年

查看全文
  • Guglielmo Beretta,
  • Alessandro Torcinovich,
  • Marcello Pelillo

摘要

In 1965, Motzkin and Straus established a profound connection between the clique number of a graph and the global maxima of a quadratic program defined on the standard simplex. Since then, a line of active and intensive research has been yielding heuristics and bounds concerning the maximum clique problem, thanks to the discoveries pertaining to local/global solutions of the Motzkin-Straus program. However, the Karush-Kuhn-Tucker (KKT) points thereof have received little to no attention in the literature. In this work, a parameterized version of the Motzkin-Straus program is discussed, and some results about its KKT points are obtained. What emerges is a connection between a generalized notion of KKT point and some regular structures contained in the graph.