Improved semidefinite branch-and-bound algorithm for k-cluster

Nathan Krislock; Jérôme Malick; Frédéric Roupin

hal-00717212, version 4

Improved semidefinite branch-and-bound algorithm for k-cluster

Nathan Krislock ( Auteur à contacter de préférence , )^a^, 1, Jérôme Malick ()^b^, 1, 2, Frédéric Roupin () ³

Résumé : This paper presents a method to solve k-cluster problems by intersecting semidefinite and polyhedral relaxations. We use a generic branch-and-bound method featuring an improved semidefinite bounding procedure. Extensive numerical experiments show that our algorithm outperforms the best known methods in both time and ability to solve large instances. For the first time, numerical results are reported for k-cluster problems on unstructured graphs with 140 and 160 vertices.

a – INRIA
b – CNRS
1 : BIPOP (INRIA Grenoble Rhône-Alpes / LJK Laboratoire Jean Kuntzmann)
INRIA – Laboratoire Jean Kuntzmann
2 : Laboratoire Jean Kuntzmann (LJK)
CNRS : UMR5224 – Université Joseph Fourier - Grenoble I – Université Pierre-Mendès-France - Grenoble II – Institut Polytechnique de Grenoble - Grenoble Institute of Technology
3 : Laboratoire d'informatique de Paris-nord (LIPN)
CNRS : UMR7030 – Université Paris XIII - Paris Nord

hal-00717212, version 4
http://hal.inria.fr/hal-00717212
oai:hal.inria.fr:hal-00717212
Contributeur : Nathan Krislock <>
Soumis le : Vendredi 13 Juillet 2012, 16:52:01
Dernière modification le : Samedi 14 Juillet 2012, 12:56:20

Voir la fiche détaillée

Documents associés

PDF :

Annexes :

Exporter

Bibtex EndNote TEI RefWorks

<?xml version="1.0" encoding="UTF-8"?>
<listBibl xmlns="http://www.tei-c.org/ns/1.0" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mml="http://www.w3.org/1998/Math/MathML">
<listBibl type="article"><head>Documents sans référence de publication (Preprint)</head>
<biblStruct type="article" xml:id="hal-00717212"><analytic>
<author><persName><forename>Nathan</forename><surname>Krislock</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Grenoble Rhône-Alpes / LJK Laboratoire Jean Kuntzmann</orgName>
<orgName type="team">BIPOP</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">Laboratoire Jean Kuntzmann</orgName>
</affiliation>
</author>
<author><persName><forename>Jérôme</forename><surname>Malick</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Grenoble Rhône-Alpes / LJK Laboratoire Jean Kuntzmann</orgName>
<orgName type="team">BIPOP</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">Laboratoire Jean Kuntzmann</orgName>
</affiliation>
<affiliation>
<orgName type="laboratory">LJK</orgName>
<orgName type="team">Laboratoire Jean Kuntzmann</orgName>
<country>FR</country>
<orgName type="institution">CNRS : UMR5224</orgName>
<orgName type="institution">Université Joseph Fourier - Grenoble I</orgName>
<orgName type="institution">Université Pierre-Mendès-France - Grenoble II</orgName>
<orgName type="institution">Institut Polytechnique de Grenoble - Grenoble Institute of Technology</orgName>
</affiliation>
</author>
<author><persName><forename>Frédéric</forename><surname>Roupin</surname></persName>
<affiliation>
<orgName type="laboratory">LIPN</orgName>
<orgName type="team">Laboratoire d'informatique de Paris-nord</orgName>
<country>FR</country>
<orgName type="institution">CNRS : UMR7030</orgName>
<orgName type="institution">Université Paris XIII - Paris Nord</orgName>
</affiliation>
</author>
<title type="main" level="a">Improved semidefinite branch-and-bound algorithm for k-cluster</title></analytic><monogr><imprint/></monogr><idno type="HALid">http://hal.inria.fr/hal-00717212</idno><idno type="HALFile">http://hal.inria.fr/hal-00717212/PDF/krislock-malick-roupin-2012a.pdf</idno></biblStruct>
</listBibl>
</listBibl>