Abstract
In this paper we consider the classical combinatorial optimization graph partitioning 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 $(V_1,\dots,V_k)$ of $V$ that minimizes $\sum_{i=1}^{k-1}\sum_{j=i+1}^{k} \max_{u \in V_i, v \in V_j} ~w(u, v)$, where $w(u,v)$ denotes the weight of the edge $\{u,v\} \in E$. We establish the $\mathcal{NP}$-completeness of the problem and its unweighted version, and the $W[1]$-hardness for the parameter $k$. Then, we study the problem for small values of $k$, and show the membership in $\mathcal{P}$ when $k=3$, but the $\mathcal{NP}$-hardness for all fixed $k \geq 4$ if one vertex per cluster is fixed. Lastly, we present a natural greedy algorithm with an approximation ratio better than $\frac{k}{2}$, and show that our analysis is tight.