1
$\begingroup$

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).

$\endgroup$
6
$\begingroup$

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}

$\endgroup$
  • $\begingroup$ I see how this algorithm would certainly optimize the objective, but I am having trouble seeing why it assures the best possible answer. $\endgroup$ – Optimizer Oct 8 '14 at 9:48
  • $\begingroup$ @Optimizer I added an alternative proof based on linear programming. $\endgroup$ – David Eisenstat Oct 8 '14 at 14:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.