Résumé
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).