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 metadatas

Cited literature [5 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00675888
Contributor : Rémi Watrigant <>
Submitted on : Friday, March 2, 2012 - 11:01:29 AM
Last modification on : Friday, May 3, 2019 - 12:08:04 PM
Long-term archiving on: Wednesday, December 14, 2016 - 9:24:55 AM

File

apex2012.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : lirmm-00675888, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

282

Files downloads

382