Sum-Max Graph Partitioning Problem - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Communication Dans Un Congrès Année : 2012

Sum-Max Graph Partitioning Problem

Résumé

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.
Fichier principal
Vignette du fichier
isco2012.pdf (1.41 Mo) Télécharger le fichier
Origine Fichiers éditeurs autorisés sur une archive ouverte
Loading...

Dates et versions

lirmm-00738554 , version 1 (04-10-2012)

Identifiants

Citer

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, ⟨10.1007/978-3-642-32147-4_27⟩. ⟨lirmm-00738554⟩
177 Consultations
1002 Téléchargements

Altmetric

Partager

More