Approximation algorithm for a problem similar to load balancing

Question

This's exercise 7ドル$ of chp 11ドル$ from the popular book algorithm design by Jon and Eva. It's about designing a 2ドル$-approximation algorithm for a problem similar to Load balancing on parallel machine. However, they said we can make an assumption on the input (in bold below), I wonder if this assumption can be dropped ?

So far my solution and any solution I can find online also use this assumption in the proof ...

---

You’re consulting for an e-commerce site that receives a large number of visitors each day. For each visitor $i$, where $i \in {1, 2, . . . , n}$, the site has assigned a value $v_i$, representing the expected revenue that can be obtained from this customer.

Each visitor $i$ is shown one of $m$ possible ads $A_1,A_2,...,A_m$ as they enter the site. The site wants a selection of one ad for each customer so that each ad is seen, overall, by a set of customers of reasonably large total weight. Thus, given a selection of one ad for each customer, we will define the spread of this selection to be the minimum, over $j = 1, 2, . . . , m$, of the total weight of all customers who were shown ad $A_j$.

Example Suppose there are six customers with values 3,ドル 4, 12, 2, 4, 6$ and there are $m = 3$ ads. Then, in this instance, one could achieve a spread of 9ドル$ by showing ad $A_1$ to customers 1,ドル 2, 4$ ad $A_2$ to customer 3ドル$ and ad $A_3$ to customers 5ドル$ and 6ドル$.

The ultimate goal is to find a selection of an ad for each customer that maximizes the spread. Unfortunately, this optimization problem is NP-hard (you don’t have to prove this). So instead, we will try to approximate it.

Give a polynomial-time algorithm that approximates the maximum spread to within a factor of 2ドル$. That is, if the maximum spread is $s$, then your algorithm should produce a selection of one ad for each customer that has spread at least $s/2$. In designing your algorithm, you may assume that no single customer has a value that is significantly above the average; specifically, if $\bar{v} = \sum_{i=1}^n v_i$ denotes the total value of all customers, then you may assume that no single customer has a value exceeding $\bar{v}/(2m)$.

• Bernardo Subercaseaux: In the example, why is the spread 9? Given $A_1$ is show to a set of customers of weight 7ドル,ドル $A_2$ to weight 3ドル$ and $A_3$ to weight 11ドル$. Or is it the max - min?
• C.C.: @BernardoSubercaseaux 1,2,4ドル$ are indices of customers, they're not values ie. $A_1$ is shown to customers with values $v[1] = 3, v[2] = 4, v[4] = 2$ totals to 9ドル$. The value vector is $v[] = \{3,4,12,2,4,6\}$.
• Bernardo Subercaseaux: Thanks, sorry I missed that.

Answer 1

This requirement can be dropped. But after that proof will be a bit more complicated.

There is an exceptional case of $m = 1$ when all customers are assigned to the only ad independently of their values, and this is the optimal solution. So further I suppose that $m \ge 2$.

If there is a customer with value $v_i > \frac{\overline v}{2m}$ we can assign to some ad $A_j$ this customer only and consider remaining visitors and ads as a subproblem. The value $v_i$ is definitely greater than or equal to a half of the natural upper bound $\frac{\overline v}{m}$ for the spread, and the same holds for the ad $A_j$.

If $\frac{\overline v - v_i}{m - 1} \ge \frac{\overline v}{m}$ then the lower bound $\frac{\overline v - v_i}{2(m - 1)}$ for our 2ドル$-approximate solution for remaining ads and customers is greater than or equal to the required lower bound $\frac{\overline v}{2m}$ for 2ドル$-approximate solution. On the other hand if $\frac{\overline{v} - v_i}{m - 1} < \frac{\overline{v}}{m}$ then the proof is the following. In any case the customer with value $v_i > \frac{\overline{v}}{2m}$ should be assigned to some ad. This ad will have value above average and therefore greater than spread. And we need to assign remaining customers to this and other ads so that $\frac{\overline{v} - v_i}{m - 1}$ becomes a new upper bound for the spread. (If we assign not only $i$-th customer to the ad $A_j$ then this new upper bound would be even less.) That's why we conclude that a solution with spread at least $\frac{\overline{v} - v_i}{2(m - 1)}$ is 2ドル$-approximation.

Thus we can remove "heavy" customers one by one while there is at least one of them (and $m \ge 2$). After that we consider the main case without "heavy" customer. And then repeating the above mentioned we inductively conclude that the whole solution (together with "heavy" customers) is 2ドル$-approximate for the original problem.

• C.C.: Thanks I understand all other cases except for the case $\frac{\bar{v}-v_i}{m-1} < \frac{\bar{v}}{m}$. Could you explain more in detail how to deal with this case ?
• C.C.: like how to "assign remaining customers to this and other ads so that $\frac{\bar{v}-v_i}{m-1}$ becomes a new upper bound for the spread." ?
• Smylic: @C.C. Since we need to assign the remaining customers to $A_j$ and $m - 1$ other ads, the average value of these $m - 1$ ads will be at most $\frac{\overline{v} - v_i}{m - 1}$. And the minimum value is always not greater than the average value. Therefore minimum is also at most $\frac{\overline{v} - v_i}{m - 1}$. That's why the optimal spread is not greater than $\frac{\overline{v} - v_i}{m - 1}$.