Solving k-cluster problems to optimality with semidefinite programming

• 成果类型: Article
• 署名作者: Malick, Jerome; Roupin, Frederic
• 署名单位: Communaute Universite Grenoble Alpes; Institut National Polytechnique de Grenoble; Universite Grenoble Alpes (UGA); Centre National de la Recherche Scientifique (CNRS); Inria; Universite Paris 13; Centre National de la Recherche Scientifique (CNRS); CNRS - Institute for Information Sciences & Technologies (INS2I)
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-012-0604-1
• 发表日期: 2012
• 页码: 279-300
• 关键词: improved approximation algorithms; relaxation

摘要

This paper deals with the computation of exact solutions of a classical NP-hard problem in combinatorial optimization, the -cluster problem. This problem consists in finding a heaviest subgraph with nodes in an edge weighted graph. We present a branch-and-bound algorithm that applies a novel bounding procedure, based on recent semidefinite programming techniques. We use new semidefinite bounds that are less tight than the standard semidefinite bounds, but cheaper to get. The experiments show that this approach is competitive with the best existing ones.