Is there a way to find the closest ratio to another ratio but in different sum?

Question

Firstly, let me apologize for my unclear title. I don't know how to describe this. Here is more description.

---

Given a ratio

$$x = x_1 : x_2 : x_3 : \cdots : x_n$$

where $s = \sum x_i$ and $x_i, n \in \mathbb{Z}^+$

Given $t$, is there any way to find the following ratio?

$$y = y_1 : y_2 : y_3 : \cdots : y_n$$ Such that

• $y$ is closest to $x$ (see below)
• $t = \sum y_i$
• $y_i \in \mathbb{Z}^+$

---

I would say $y$ is closest to $x$, if and only if, there is no other ratio

$$z = z_1 : z_2 : z_3 : \cdots : z_n$$

where $\sum z_i = t$ and $z_i \in \mathbb{Z}^+$

Such that:

$$\sum|\frac{z_i}{t} - \frac{x_i}{s}| < \sum|\frac{y_i}{t} - \frac{x_i}{s}|$$

---

My intuitive possible solution is: $$y_i = t \times \operatorname{round}(x_i \div s)$$

However, this is obviously stupid. Take the ratio $1:1$, and let's say we are looking for $t=5$.

Then following my proposal:

$$ x = 1:1\\ y = (5 \times \operatorname{round}(0.5)):(5 \times \operatorname{round}(0.5)) = 5:5 $$

Obviously, since $5+5= 10 \neq 5$, it violates my requirement $\sum y_i = t$. The correct answer of this example should be $2:3$ or $3:2$.

---

Thanks in advance.

Answer 1

The first thing to do is make it $y_i=\operatorname{round}(tx_i/s)$ so you get more granularity in your rounding. A lot of work has been put into this for apportioning representatives. For example, the US House of Representatives is fixed at $435$ seats which are to be allocated to the states in proportion to population. Of course, if you just divide the population of the country by $435$ and say you get one representative for each set of that many people you get a lot of fractional representatives. The naive thing, and what is done above, is to round but that doesn't guarantee the sum is $435$. Basically what is done (after you guarantee each state at least one representative) is to set a breakpoint for rounding that may well not be $0.5$ but is chosen so the proper number of states round up to give the total $435$. The competing concept is to adjust the multiplier $t/s$ a bit so that rounding with a breakpoint of $0.5$ results in the proper sum. That impacts the large $x_i$ more than the small $x_i$ so if your initial distribution with multiplier $t/s$ and breakpoint $0.5$ leaves you short they will be more likely to be assigned to the larger $x_i$ compared to just shifting the breakpoint. I don't know a proof that either one of these approaches is optimal for the metric of closest you have selected.

Answer 2

I am not sure, but this looks like it might be an NP-hard problem. Even if it is not, it seems unlikely that we will come up with a straightforward, provably optimal solution that doesn't take exponential time in the worst case.

Since you have a well-defined and easily evaluated "error" function, there is a brute-force solution: try all possible sequences of numbers $y_1,\ldots,y_n$ that have the sum $t,$ and choose the sequence for which the error is smallest. Applying a little more cleverness, you might use branch-and-bound search techniques to reduce the number of "obviously wrong" sequences of numbers that you look at.

Alternatively, you could try some heuristic methods and hope they get the best possible result or at least give you something close enough to the best result. Some methods were suggested in another answer.

If you're willing to take a few more steps to get an answer, you might start with $y_i=1$ for all $i$ and then add $1$ to whichever term will reduce the error the most. That is, starting each of the numbers at a minimum value, use a "greedy" algorithm to try to approach the ideal ratio as quickly as possible. Using efficient data structures to keep track of which terms to consider increasing next, I think the gives you an algorithm with a time complexity something like $t\log n.$

A variation of the above would be to use a reasonably good rounding formula to get an initial list of numbers, and then use a greedy algorithm to add or subtract from the numbers until you get as close as this method can get to the ideal result.