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.

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.

  • 1
    Using your first hint, I would say to double items that make the most 'difference' to the average, and do this to find out the maximum possible weighted average. I've tried some more greedy methods, such as picking the highest weight*value, as well as the highest valued items. However, none of these options seem to be correct. Do you mean a subset of items to double their weight, or just a subset of items on its own? – Dr C Dec 12 '17 at 7:21
  • @DrC, don't guess -- if you think you have an algorithm, the next step is to prove it correct! (or find a counterexample demonstrating that it is not correct) – D.W. Dec 12 '17 at 8:02

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

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.

  • You can use MathJax to formal the formulas in your post. – Yuval Filmus Dec 12 '17 at 21:28
  • I did try this method, and it seems to be correct so far with random testing. Note that just calculating $ [(x+(vw))/(y+w)]$ would be enough, since we can drop the $x/y$ term while still preserving inequality. Now the problem becomes figuring out a proof, and making it more efficient. I am considering induction – Dr C Dec 13 '17 at 7:19
  • Yes, I was considering commenting that x/y is a constant so it can be dropped, but I thought it might be useful for debugging to see what the actual differences are. Also an optimisation, you can store the new numerator and denominator with each value pairing, which will mean you instantly know the new weighted average after doubling, and you don't need to re-calculate it next pass. – Leo Imrie Dec 13 '17 at 9:58
  • One thing I did want to ask - in your original question you stated: "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". It seems to me that to bruteforce it, you'd need to test every item, then every 2pickn items etc. up to (n-1)pickn items. This seems that the complexity would be closer to n^n, rather than 2^n, no? – Leo Imrie Dec 13 '17 at 9:59
  • And one other thing: I have no idea how to break ties with this method (i.e. highest value, lowest value, highest weighting or lowest weighting). If you need to branch every time there is a tie for the largest difference, that does increase the worst case running time by a fair whack. – Leo Imrie Dec 13 '17 at 10:08

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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