Sum-Max Graph Partitioning Problem - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Conference Papers Year : 2012

Sum-Max Graph Partitioning Problem

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.
Fichier principal
Vignette du fichier
isco2012.pdf (1.41 Mo) Télécharger le fichier
Origin Publisher files allowed on an open archive
Loading...

Dates and versions

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

Identifiers

Cite

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⟩
140 View
965 Download

Altmetric

Share

More