Solving k-cluster problems to optimality with semidefinite programming |
| |
Authors: | Jér?me Malick Frédéric Roupin |
| |
Affiliation: | 1. CNRS, Lab. Jean Kuntzmann, Grenoble, France 2. Universit?? Paris 13, Sorbonne Paris Cit??, LIPN, CNRS, UMR 7030, 93430, Villetaneuse, France
|
| |
Abstract: | This paper deals with the computation of exact solutions of a classical NP-hard problem in combinatorial optimization, the $k$ -cluster problem. This problem consists in finding a heaviest subgraph with $k$ 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|