Skip to Main content Skip to Navigation
Conference papers

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
* Corresponding author
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).
Complete list of metadata

Cited literature [5 references]  Display  Hide  Download
Contributor : Rémi Watrigant <>
Submitted on : Friday, March 2, 2012 - 11:01:29 AM
Last modification on : Thursday, June 11, 2020 - 8:56:02 PM
Long-term archiving on: : Wednesday, December 14, 2016 - 9:24:55 AM


Files produced by the author(s)


  • HAL Id : lirmm-00675888, version 1



Rémi Watrigant, Marin Bougeret, Rodolphe Giroudeau, Jean-Claude König. On the Approximability of the Sum-Max Graph Partitioning Problem. APEX: Approximation, Parameterized and EXact algorithms, Feb 2012, Paris, France. ⟨lirmm-00675888⟩



Record views


Files downloads