Convert float array to lower or higher integer, find sum(integers) == round(sum(floats)), reducible to subset sum?

Question

You have an array of floats, for example:

[74.45329758275943, 501.9063197679927, 172.59563201929095, 
 307.1739798358187, 362.042263381624, 940.1282277740091, 
 577.2604546481798, 63.201270419598224, 828.8081043649505, 31.1630295128974]

For each float, you can either call floor() or ceiling() to convert it to the nearest integer. The goal is to solve these two questions:

1. Choose floor or ceiling on each float to produce a set of integers where sum(integers) = round(sum(floats)).
2. Of the values that solve question 1, find the floor or ceiling choice that produces min(abs(float - int)), for each float/integer pair.

I think this is reducible to subset sum, and indicated as much during the quiz I just completed, but I wanted to check with people who have done reductions more frequently than me.

• Compute round(sum(floats) and subtract this value from each float in the array.
• Then for each of these "subtracted" floats, compute both floor and ceiling and put them in a new array with 2x the length of the old array.
• You now need to find a subset of these values, including both positive and negative integers, that sums to 0. However, you either need to choose the floor or the ceiling value for each of the original inputs, which limits the number of subsets that need to be searched.

I have not done an algorithms class in some time; is the analysis above correct, or am I missing something? Is this problem NP complete or is there a polynomial time solution?

Answer 1

Here is how I would solve this:

Denote $A$ as the array, which has $n$ values $A_1,\dots,A_n$. Without loss of generality, I will assume that there is no integer in $A$ (think of how to deal with the case that there is one!)

Lets start by computing $d:=round\left(\sum_{i=1}^NA_i\right)-\sum_{i=1}^n{\lfloor A_i \rfloor}$. Notice, that this tells us exactly for how many values we need to choose "ceiling" instead of floor: since each time we choose "ceiling" instead of "floor", we increase the total sum by $1$.

Therefore, for question $1$, the answer should be "choose any $d$ values you want to round up, and the rest to round down".

For question $2$, even though we already know we need exactly $d$ "round up"s, we need to choose them carefully in order to minimize the differences. But first, I want to clarify how I understood the question: The question, as I see it - asks us to minimize $\sum_{i=1}^n { |A_i-R_i| }$ where $R_i$ is the rounded $A_i$, and also the solution has to satisfy that $\sum_{i=1}^n R_i = round \left(\sum_{i=1}^n A_i\right)$. The latter, we already saw how to achieve. Now whats left is to choose which things we round up correctly so we will minimize $\sum_{i=1}^n |A_i-R_i|$.

For this task, let us compute a value $v_i$ for every index $1\le i\le n$, such that $v_i:= (A_i - \lfloor A_i \rfloor) - (\lceil A_i \rceil - A_i)$. Please take a moment to understand why $v_i$ is the "loss" (or "gain") when we choose to round $A_i$ up instead of down.

Now, we can rewrite the cost for $A_i$ when we choose to round it up, as $|A_i-\lfloor A_i\rfloor | +v_i $, and when we choose to round it down, the cost is $|A_i-\lfloor A_i \rfloor|$. Notice, how in both cases we had $|A_i-\lfloor A_i \rfloor |$. This means, that we can rewrite the total cost as follows: $Total~cost=\sum_{i=1}^n { |A_i-R_i| }=\sum_{i=1}^n |A_i - \lfloor A_i \rfloor| + s_iv_i$, where $s_i\in \{0,1\}$ is $1$ if we choose to round $A_i$ up, and $0$ if we choose to round it down.

In this sum, we cannot control the value of $|A_i-\lfloor A_i \rfloor |$ whatsoever, so when minimizing, all such terms disappear. This makes us now minimize the value of $\sum_{i=1}^n s_iv_i$ (with exactly $d$ values of $s_i$ being $1$, and the rest being $0$), which is equivalent to finding the $d$ smallest $v_i$s, and choosing to round up the $A_i$s that correspond to them - rounding down the rest of the values.

---

As you can see, this is a polynomial solution to the question. The problem with your reduction is that you did it the wrong direction. To show that a problem $L$ is NP-hard, using reductions - you need to show a reduction from subset sum, to $L$. What you showed is the other direction, hence the reduction doesn't imply that your problem is hard.

Answer 2

It's really quite simple.

Step 1: Calculate the target sum, which is round (sum (x_i)). Let's say you get a value of 597.

Step 2: Calculate the sum that you get if you round every number down, that is sum (floor (x_i)). Let's say you get a value of 594.

Step 3: Calculate how many values must be rounded up. In this case, 597 - 594 = 3 x_i must be rounded up to get the required sum of 597.

Step 4: Determine which values to round up. You do this by finding (in this case) the three values where ceil (x_i) - x_i is largest.

Each of these steps is easily done in O (n) steps. So if you mentioned "subset-sum" problem to me and started to talk about NP and NP-complete, I'd be quite suspicious about your job application.

You would get bonus points if you talked about rounding errors and how to make sure that round (sum (x_i)) is calculated correctly in the face of rounding errors. Or if you improved the speed and reduced rounding errors by combining my Step 1 and Step 2 into one (that's what nir shahar's solution does).

Answer 3

As stated, the part 2 may easily fail to be possible.

Take the numbers $0.2, 0.3, 0.4$. The rounded sum is $1$, but "min(abs(float - int))" rounds all three to $0$.