Sum-Max Graph Partitioning Problem

Rémi Watrigant 1 Marin Bougeret 1 Rodolphe Giroudeau 1 Jean-Claude König 1
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 paper we consider the classical combinatorial optimization graph partitioning problem, with Sum-Max as objective function. Given a weighted graph G = (V, E) and a integer k, our objective is to find a k-partition $(V_1,...,V_k)$ of V that minimizes $\sum_{i=1}^{k-1}\sum_{j=i+1}^{k}\max_{u \in V_i, v \in V_j} w(u,v)$, where w(u,v) denotes the weight of the edge ${u,v} \in E$. We establish the NP-completeness of the problem and its unweighted version, and the W[1]-hardness for the parameter k. Then, we study the problem for small values of k, and show the membership in P when $k = 3$, but the NP-hardness for all fixed $k \ge 4$ if one vertex per cluster is fixed. Lastly, we present a natural greedy algorithm with an approximation ratio better than k/2, and show that our analysis is tight.
Type de document :
Communication dans un congrès
ISCO: International Symposium on Combinatorial Optimization, Apr 2012, Athens, Greece. pp.297-308, 2012, 〈http://isco12.cs.aueb.gr〉. 〈10.1007/978-3-642-32147-4_27〉
Liste complète des métadonnées

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

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00738554
Contributeur : Rémi Watrigant <>
Soumis le : jeudi 4 octobre 2012 - 15:34:43
Dernière modification le : jeudi 24 mai 2018 - 15:59:22
Document(s) archivé(s) le : vendredi 16 décembre 2016 - 21:37:11

Fichier

isco2012.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

Collections

Citation

Rémi Watrigant, Marin Bougeret, Rodolphe Giroudeau, Jean-Claude König. Sum-Max Graph Partitioning Problem. ISCO: International Symposium on Combinatorial Optimization, Apr 2012, Athens, Greece. pp.297-308, 2012, 〈http://isco12.cs.aueb.gr〉. 〈10.1007/978-3-642-32147-4_27〉. 〈lirmm-00738554〉

Partager

Métriques

Consultations de la notice

146

Téléchargements de fichiers

618