patternMinor
Minimum weighted arithmetic mean partion?
Viewed 0 times
weightedmeanminimumpartionarithmetic
Problem
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).
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).
Solution
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$).
$$ 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$).
Context
StackExchange Computer Science Q#24232, answer score: 4
Revisions (0)
No revisions yet.