Maximizing the weighted average value of a set of items by doubling the weight of a subset of items

Question

Given a set of $n$ items, each represented by $t_i=(w_i,v_i)$ for $1 \le i \le n$, the weighted average value of those items is defined as: $$ \frac{\sum_{i=1}^{n}v_iw_i}{\sum_{i=1}^nw_i} $$

The goal is to find a subset of items to double their weight, such that the weighted average value is maximized.

For example, suppose you have the following set of items, where $t_i = (w_i,v_i)$:

$$ t_1 = (12, 1100000)\\ t_2 = (12, 1000000)\\ t_3 = (12, 850000)\\ t_4 = (10, 800000) \\ t_5 = (8, 1200000) $$ The weighted average value is 981,481. The best solution is to double the weight of items 1 and 5, which leads to a new weighted average of 1,024,324.

I am trying to come up with an algorithm to find the best subset of items to double, and so far I've tried using bruteforce. For each item, you can choose to either double it, or leave it as it is. This means that there are a total of $2^n$ possibilities to explore, which means exponential complexity. I've also tried a greedy algorithm to pick the highest value-to-weight ratio items, and determine the best number of items to pick, however this solution is not always optimal.

I am wondering, what is the most efficient algorithm to find the best subset of items to double their weight?

Thanks in advance.

Answer 1

Suppose $v_1>\cdots>v_n$ without loss of generality, there is an greedy algorithm working as follows.

vw = v_1 * w_1 + ... + v_n * w_n
w = w_1 + ... + w_n
for i = 1 to n:
    if v_i > vw / w:  // #1
        choose item i to double its weight
        vw += v_i * w_i
        w += w_i

Note condition #1 means doubling $w_i$ will enlarge the current weighted average value. Also note vw / w does not decrease, so finally $w_1,w_2,\ldots,w_k$ are doubled for some $k$.

To prove the correctness of the algorithm, we only need to prove the algorithm behaves correctly in each step, i.e. if whether $w_1,\ldots,w_{i-1}$ are doubled are already determined (for convenience, in the following analysis, $w_j$ $(j=1,\ldots,i-1)$ represents the value after doubling if it is determined to be doubled), then

1. if $v_i > \sum_{j=1}^n v_jw_j/\sum_{j=1}^n w_j$, then there is an optimal solution that doubles $w_i$, and
2. if $v_i \le \sum_{j=1}^n v_jw_j/\sum_{j=1}^n w_j$, then there is an optimal solution that does not double $w_i$.

Let's firstly prove statement 1 by contradiction. Assume no optimal solution doubles $w_i$, and suppose an optimal solution chooses to double $w_{i_1}, w_{i_2},\ldots, w_{i_m}$ where $i< i_1<\cdots <i_m$. We can assume $m\ge1$, otherwise the optimal solution doubles none of $v_i,v_{i+1},\ldots,v_n$, then doubling $v_i$ will make this solution better since $v_i > \sum_{j=1}^n v_jw_j/\sum_{j=1}^n w_j$, a contradiction. Note doubling $w_i,w_{i_1}, w_{i_2},\ldots, w_{i_m}$ is not an optimal solution, we have $$\frac{\sum_{j=1}^n v_jw_j+\sum_{j=1}^mv_{i_j}w_{i_j}}{\sum_{j=1}^n w_j+\sum_{j=1}^mw_{i_j}}>v_i.$$

Also note the optimal solution is no worse than the solution that doubles $w_{i_2},\ldots,w_{i_m}$, we have

$$\frac{\sum_{j=1}^n v_jw_j+\sum_{j=1}^mv_{i_j}w_{i_j}}{\sum_{j=1}^n w_j+\sum_{j=1}^mw_{i_j}}\le v_{i_1}.$$

Hence $v_{i_1}>v_i$, a contradiction.

Now let's prove statement 2. Suppose an optimal solution doubles $w_{i_1},\ldots, w_{i_m}$ where $i\le i_1<\cdots <i_m$, since $v_i \le \sum_{j=1}^n v_jw_j/\sum_{j=1}^n w_j$, we have

$$\frac{\sum_{j=1}^mv_{i_j}w_{i_j}}{\sum_{j=1}^mw_{i_j}}\le v_i \le \frac{\sum_{j=1}^n v_jw_j}{\sum_{j=1}^n w_j},$$ thus $$\frac{\sum_{j=1}^n v_jw_j+\sum_{j=1}^mv_{i_j}w_{i_j}}{\sum_{j=1}^n w_j+\sum_{j=1}^mw_{i_j}}\le \frac{\sum_{j=1}^n v_jw_j}{\sum_{j=1}^n w_j},$$

which means not doubling any of $w_i,w_{i+1},\ldots, w_n$ is also an optimal solution, i.e. there is indeed an optimal solution that does not double $w_i$.

Answer 2

This can be solved in polynomial time.

Hint: consider the decision version of the problem.

Suppose I gave you a value $\alpha$ and asked you whether it's possible to find a subset of items so that the weighted average is at least $\alpha$.

Could you solve that version of the problem? Does this give you any ideas about how to solve the original problem?

---

Alternate hint:

Keep trying other greedy strategies. You've tried one greedy algorithm, but there might be other plausible greedy algorithms.

Answer 3

I think the below gives the correct answer, but I am not sure how to prove it.

1. For every pairing, work out the difference it would make to the weighted average if the weight were doubled. This is given by $\frac{x+vw}{y+w}-\frac{x}{y}$ where:

   • $x$ is the numerator of the weighted average
   • $v$ is the value of the current pairing
   • $w$ is the weight of the current pairing
   • $y$ is the denominator of the current weighted average

2. Pick the largest positive difference and double the weight. If there are no positive differences, stop.

3. Repeat, ignoring the value you just doubled.

It seems intuitively that in the worst case, you will end up doubling all but one values, in which case you will make $2n(n+1)/n$ passes (factor of 2 in the numerator to find the largest difference after working them all out: two passes over the dataset per iteration).

I think this is the best naive solution, but can surely be optimised further for practical applications.