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,\dots,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 $\mathcal{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 $\mathcal{P}$ when $k=3$, but the $\mathcal{NP}$-hardness for all fixed $k \geq 4$ if one vertex per cluster is fixed. Lastly, we present a natural greedy algorithm with an approximation ratio better than $\frac{k}{2}$, and show that our analysis is tight.
Type de document :
Rapport
RR-12015, 2012
Liste complète des métadonnées

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

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00694569
Contributeur : Rémi Watrigant <>
Soumis le : mardi 2 octobre 2012 - 14:14:10
Dernière modification le : jeudi 11 janvier 2018 - 06:26:15
Document(s) archivé(s) le : vendredi 31 mars 2017 - 13:52:01

Fichier

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

Identifiants

  • HAL Id : lirmm-00694569, version 2

Collections

Citation

Rémi Watrigant, Marin Bougeret, Rodolphe Giroudeau, Jean-Claude König. Sum-Max Graph Partitioning Problem. RR-12015, 2012. 〈lirmm-00694569v2〉

Partager

Métriques

Consultations de la notice

135

Téléchargements de fichiers

735