On the Approximability of the Sum-Max Graph Partitioning Problem

Rémi Watrigant 1, * Marin Bougeret 1 Rodolphe Giroudeau 1 Jean-Claude König 1
* Auteur correspondant
1 MAORE - Méthodes Algorithmes pour l'Ordonnancement et les Réseaux
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : In this talk we consider the classical combinatorial optimization graph partitioning problem with Sum-Max as objective function. Given a weighted graph on n vertices and an integer k, our objective is to find a k-partition of its vertices such that the sum of the largest edge weight between each pair of clusters is minimized. We prove, in addition to the NP and W[1] hardnesses (for the parameter k), that there is no p-approximation algorithm for any p in O(n^{1-\epsilon}), given any fixed 0 < \epsilon <= 1 (unless P=NP). Lastly, we present a natural greedy algorithm with an approximation ratio bounded by k/2 (notice that this bound is tight).
Type de document :
Communication dans un congrès
International Workshop on Approximation, Parameterized and EXact algorithms, Feb 2012, Paris, France. pp.3, 2012, 〈http://apex.lip6.fr/〉
Liste complète des métadonnées

Littérature citée [5 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00675888
Contributeur : Rémi Watrigant <>
Soumis le : vendredi 2 mars 2012 - 11:01:29
Dernière modification le : jeudi 24 mai 2018 - 15:59:22
Document(s) archivé(s) le : mercredi 14 décembre 2016 - 09:24:55

Fichier

apex2012.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : lirmm-00675888, version 1

Collections

Citation

Rémi Watrigant, Marin Bougeret, Rodolphe Giroudeau, Jean-Claude König. On the Approximability of the Sum-Max Graph Partitioning Problem. International Workshop on Approximation, Parameterized and EXact algorithms, Feb 2012, Paris, France. pp.3, 2012, 〈http://apex.lip6.fr/〉. 〈lirmm-00675888〉

Partager

Métriques

Consultations de la notice

231

Téléchargements de fichiers

244