On the Approximability of the Sum-Max Graph Partitioning Problem
Rémi Watrigant, Marin Bougeret, Rodolphe Giroudeau, Jean‐Claude König · 2012
Abstract In this paper we consider the classical combinatorial optimization graph parti-tioning 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 (V1,..., Vk) of V that minimizes∑k−1 i=1 ∑k j=i+1maxu∈Vi,v∈Vj w(u, v), where w(u, v) denotes the weight of the edge {u, v} ∈ E. We prove, in addition to the NP and W [1] hardnesses (for the parameter k), that there is no ρ-approximation algorithm for any ρ ∈ O(n1−), given any fixed 0 < ≤ 1 (unless P = NP), improving the previous 1+ 1 k lower bound of [5]. Lastly, we present a natural greedy algorithm with an approximation ratio better than k 2