Proving NP hardness of maximum sum of means of a partition into k sets

Question

I am trying to show the following problem is NP-hard and would like some help.

Inputs: Integer $k$, and unordered set of $N$ numbers, $O$

Output: the $\max \sum\limits_{S_i \in S} \operatorname{mean}(S_i)$

where $S=\{S_1,S_2,...,S_k\}$, $O=S_1 \cup S_2 \cup \dots \cup S_k$ and elements of $S$ are disjoint.

In simpler terms, partition $O$ into $k$ sets to maximize the total sum of the means of the sets.

This problem is a special case of a graph partition problem I am trying to prove NP-hard. I suspect even this special case that removes the graph structure is NP-hard and might be easier to prove. I have tried to reduce from the partition problem (minimize difference of sum of 2 sets).

Answer 1

Put each of the $k-1$ greatest numbers in their own set, and the remaining numbers all together in the $k$th set. This linear-time algorithm can be proved correct by using the following (non-strictly) improving moves to reach the specified optimal solution from any other.

1. Given two numbers $a<b$ with $a\in S_i$ and $b\in S_j$ and $\lvert S_i\rvert\le\lvert S_j\rvert$, swap $a$ and $b$.

2. Given $S_i,S_j$ where $|S_i|\ne 1$ and where all of the numbers in $S_i$ are greater than or equal to all of the numbers in $S_j$, move the smallest number in $S_i$ to $S_j$. (This move does not decrease the average of $S_i$, and does not decrease the average of $S_j$.)

An alternative correctness proof uses a linear relaxation. Let the numbers be $a_1\ge\cdots\ge a_n$ and consider the following linear program.

\begin{align} &\text{maximize }\sum_{i=1}^na_ix_i\\ &\text{subject to}\\ &\sum_{i=1}^nx_i=k&(w)\\ &\forall i\in\{1,\ldots,n\},\quad-x_i\le\frac{-1}{n-(k-1)}&(y_i)\\ &\forall i\in\{1,\ldots,n\},\quad x_i\le1&(z_i) \end{align}

Given a partition, for all $i\in\{1,\ldots,n\}$, we can set $x_i=1/\lvert S_j\rvert$, where $a_i\in S_j$. It follows that this program is in fact a relaxation. The proposed partition sets $x_1,\ldots,x_{k-1}=1$ and $x_k,\ldots,x_n=1/(n-(k-1))$.

Here is the dual program. By weak duality, feasible solutions of this program upperbound the objective value of the primal.

\begin{align} &\text{minimize }kw+\sum_{i=1}^n\left(\frac{-y_i}{n-(k-1)}+z_i\right)\\ &\text{subject to}\\ &\forall i\in\{1,\ldots,n\},\quad w-y_i+z_i=a_i&(x_i)\\ &\forall i\in\{1,\ldots,n\},\quad y_i,z_i\ge0\\ \end{align}

Here is a feasible solution to the dual program whose objective value is equal to the previously proposed primal solution. It follows that both solutions are optimal.

\begin{align} w&=a_k\\ y_i&=\begin{cases}a_k-a_i&\text{if }i\in\{k,\ldots,n\}\\0&\text{otherwise}\end{cases}\\ z_i&=\begin{cases}a_i-a_k&\text{if }i\in\{1,\:\ldots,\:k-1\}\\0&\text{otherwise}\end{cases} \end{align}