On the Approximability of the Sum-Max Graph Partitioning Problem - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2012

On the Approximability of the Sum-Max Graph Partitioning Problem

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).
Fichier principal
Vignette du fichier
apex2012.pdf (348.58 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

lirmm-00675888 , version 1 (02-03-2012)

Identifiers

  • HAL Id : lirmm-00675888 , version 1

Cite

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⟩
156 View
205 Download

Share

Gmail Facebook X LinkedIn More