Given triples of $n$ floating point values
$$(\min_1, \max_1, w_1), \dots, (\min_n, \max_n, w_n)$$
and a value $V$, what is a good algorithhm to assign values $v_i$ to each of the triples such that the following conditions hold?
- $\min_i \le v_i \le \max_i$.
- $\displaystyle\sum_{i=1}^n v_i = V$.
- $\dfrac{v_i}{V}$ is as close as possible to $\dfrac{w_i}{W}$, where $W = \displaystyle\sum_{i=1}^n w_i$, i.e., minimize $\displaystyle\sum_{i=1}^n \left| \frac{v_i}{V} - \frac{w_i}{W} \right|$.
I understand the above can be solved via an LP solver but am looking for an algorithm that may not return the optimal assignment but that is deterministic, returns close to the optimum solutions, runs in $O(n)$ time, and returns solutions that are stable in the sense that if two instances of the problem definition are "close to each other" then the solutions tend to be close to each other.
It seems like there should be a greedy approach the performs sufficiently in which the first step is assigning the minima to $v_i$ and then proportioning out the "slack" but I am not sure how to deal with the maxima while doing this.