Centre d'Etude et De Recherche en Informatique et Communications (EA4629) |
|
Solving k-cluster problems to optimality using adjustable semidefinite programming bounds
[MR10d] Solving k-cluster problems to optimality using adjustable semidefinite programming bounds
Rapport Scientifique : Date de dépot: 2010/01/01, (Tech. Rep.: CEDRIC-10-1920) (Soumis)
motcle:
Résumé:
This paper deals with computing exact solutions of a classical NP-hard problem of combinatorial optimization, the k-cluster problem. This problem consists in finding a heaviest subgraph with k nodes in a
weighted graph, (or a densest subgraph, if the graph is
unweighted). We present a branch-and-bound approach that applies a
novel bounding procedure, based on recent semidefinite programming
techniques. We use new semidefinite bounds that are less accurate than the
standard semidefinite bounds, but cheaper to get. The experiments show
that this approach is competitive with the best existing ones.
Collaboration:
LIPN
| @techreport { | |||
| MR10d, | |||
| title | = | "{Solving k-cluster problems to optimality using adjustable semidefinite programming bounds}", | |
| author | = | "J. Malick and F. Roupin", | |
| number | = | "{CEDRIC-10-1920}", | |
| institution | = | "{CEDRIC laboratory, CNAM-Paris, France}", | |
| date | = | {01-01-2010}, | |
| note | = | "{Soumis}", | |
| } | |||
Agenda
 Suivre le laboratoire
|
ContactsCNAM-CEDRIC ENSIIE-CEDRIC |