3
$\begingroup$

Assume I have some positive numbers $a_1,\ldots,a_n$ and a number $k \in \mathbb{N}$.

I want to partition these numbers into exactly $k$ sets $A_1,\ldots,A_k$ such that the weighted arithmetic mean

$$\text{cost}(A_i,\ldots,A_k)=\sum_{i=1}^{k}\frac{|A_i|}{n}c(A_i)$$

is minimal, where $c(A_i)=\sum_{a \in A_i}a$ is simply the sum of all numbers in $A_i$.

Is there actually a (polynomial) algorithm to do this or is this a (NP) hard problem?

I tried to reduce it to some NP-hard problems but didn't get anywhere, especially because the numbers are nonnegative and thus in an optimal partition big sets need to have smaller weight which seems to be some kind of balancing problem instead of a packing problem (which I am more familiar with).

$\endgroup$
3
$\begingroup$

Suppose first that we fix the sizes of the sets $|A_i| = n_i$ in non-decreasing order $n_1 \leq \cdots \leq n_k$. In that case, if we arrange the numbers $a_i$ in non-decreasing order, then an optimal choice is $$ A_1 = \{a_n,\ldots,a_{n-n_1+1}\}, A_2 = \{a_{n-n_1},\ldots,a_{n-n_1-n_2+1}\}, \ldots, A_k = \{a_{n_k},\ldots,a_1\}. $$ The reason is that given any solution where $a_i \in A_I$ and $a_j \in A_J$, switching $a_i$ and $a_j$ will result in a total change of $$ -n_Ia_i-n_Ja_j + n_Ja_i+n_Ia_j = (n_I-n_J) (a_j-a_i),$$ so the switch is beneficial (or harmless) as long as $n_I \leq n_J$ and $a_j \geq a_i$.

In view of this, there is always an optimal solution in which $A_1,\ldots,A_k$ is a partition of $a_1,\ldots,a_n$ into intervals. This suggests a dynamic programming algorithm. For each $\ell \leq k$ and $t \leq m \leq n$, we compute $$ \min_{A_1,\dots,A_{\ell-1} \vdash a_1,\ldots,a_t} \sum_{i=1}^\ell |A_i| c(A_i), \quad \text{where $A_\ell = \{a_{t+1},\ldots,a_m\}$}. $$ Here $A_1,\dots,A_{\ell-1} \vdash a_1,\ldots,a_t$ means that the left-hand side is a partition of the right-hand side into intervals. I am assuming that sets could be empty; the algorithm can be modified to ensure that sets are not empty (just make sure $\ell \leq t < m$).

$\endgroup$
  • $\begingroup$ Thank you! Fixing the size of the sets really makes the problem easier, I missed that. Needless to say I am really surprised that there actually is an algorithm to solve this in subexponential time. $\endgroup$ – Listing Apr 30 '14 at 9:04

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.