Rounding to minimise the sum of errors in pairwise distances What is known about the complexity of the following problem:


Given: rational numbers $x_1 &lt; x_2 &lt; \dotso &lt; x_n$.
Output: integers $y_1 \le y_2 \le \dotso \le y_n$.
Objective: minimise $$\sum_{1 \le i &lt; j \le n} e(i,j),$$ where $$e(i,j) = | (y_j-y_i) - (x_j-x_i)|.$$


That is, we would like to round the rational numbers to integers so that we minimise the sum of errors in pairwise distances. For each pair $i, j$ we would like to have the rounded distance $y_j-y_i$ as close as possible to the true distance $x_j-x_i$.



Motivation: a boring metro trip, and a poster that shows the "locations" of the stations at the resolution of one minute of travelling time. Here we are minimising the error that people make if they use the poster to look up the travelling time between stations $i$ and $j$, averaging over all pairs $i&lt;j$.



(source)

For example, here we can read the following approximations of the pairwise distances between the four stations (using A, B, C, D for brevity):


A–B ≈ 1 minute, B–C ≈ 2 minutes, C–D ≈ 2 minutes
A–C ≈ 3 minutes, B–D ≈ 4 minutes
A–D ≈ 5 minutes


Is this the best possible approximation? If you knew the actual travelling times, could you find a better solution?



At first, this sounded like a simple exercise in dynamic programming, but now it seems that some amount of actual thinking is required.

Does anyone recognise this problem? Or see a clever algorithm for solving it?



Edit: There are some natural variants of the question that have been mentioned in the comments; let's give them some names:


floor/ceil version: it is required that $y_i \in \{ \lfloor x_i \rfloor, \lceil x_i \rceil \}$ for all $i$.
integer version: it is sufficient that $y_i \in \mathbb{Z}$ for all $i$.
monotonic version: it is required that $y_1 \le y_2 \le \dotso \le y_n$.
non-monotonic version: we can have $y_i &gt; y_j$ for $i &lt; j$.


The original question considers the monotonic integer version, but answers related to any of these versions are welcome.
OK. The DP algorithm seems to be unnecessarily complicated. After reading comments I think this might solve the Monotonic version of the problem (but I have not checked every detail).

First, assume each $x_i = \lfloor x_i\rfloor +\{x_i\}$, where $\lfloor x_i\rfloor$ is the integral part, $\{x_i\}$ is the fractional part. Assume $x_i$ is rounded to $\lfloor x_i \rfloor + v_i$, where $v_i$ is a nonnegative integer (of course in general $v_i$ can be negative, but we can always shift so that the smallest $v_i$ is 0). 

Now, consider the cost for a pair $x_i$, $x_j$ when doing this rounding. The cost should be

$$
||v_i-v_j+ \lfloor x_i\rfloor -  \lfloor x_j\rfloor| - |\{x_i\}-\{x_j\} + \lfloor x_i\rfloor - \lfloor x_j\rfloor||
$$

The expression is complicated because of the absolute values. However, notice that we have monotonicity, so the things inside the two inner absolute values should have the SAME sign. Since we have an outer absolute value, it really doesn't matter what that sign is, the expression just simplifies to

$$
|v_i-v_j - (\{x_i\} - \{x_j\})|
$$

From now on we do not assume the solution is monotonic, but instead, we change the objective to minimize the sum of the above term for all pairs. If the solution to this problem happens to be monotonic, then of course it is also the optimal solution for the monotonic version. (Think of this as: original problem has an infinite penalty when the solution is not monotonic, the new problem has smaller penalty, if a monotonic solution wins even in the new version, it must be the solution to the monotonic version)

Now we would like to prove, if $\{x_i\} &gt; \{x_j\}$, in the optimal solution we must have $v_i \ge v_j$.

Assume this is not true, that we have a pair $\{x_i\} &gt; \{x_j\}$ but $v_i &lt; v_j$. We shall show that if we swap $v_i$ $v_j$ the solution gets strictly better.

First we compare the term between $i$ and $j$, here it is really clear that swapping is strictly  better because in the non-swap version, $v_i-v_j$ and $\{x_j\}-\{x_i\}$ has the same sign, the absolute value will be the sum of the two absolute values.

Now for any $k$, we compare the sum of pairs $(i,k)$ and $(j,k)$. That is, we need to compare

$|v_i-v_k-(\{x_i\}-\{x_k\})|+|v_j-v_k-(\{x_j\}-\{x_k\})|$ and $|v_j-v_k-(\{x_i\}-\{x_k\})|+|v_i-v_k-(\{x_j\}-\{x_k\})|$.

Use $A$, $B$, $C$, $D$ to denote the four terms inside the absolute value, it is clear that $A+B = C+D$. Also it is clear that $|A-B| \ge |C-D|$. By convexity of the absolute value, we know $|A|+|B| \ge |C|+|D|$. Take the sum over all $x_k$'s, we know swapping can only be better.

Notice that now we already have a solution for the Monotonic floor/ceil version: there must be a threshold, when $\{x_i\}$ is bigger always round up, when it is smaller always round down, when it is equal round some up and some down, while the solution quality only depends on the number. We enumerate all these solutions and pick the one with smallest objective function. (All these solutions are necessarily monotonic).

Finally we would like to go to the monotonic integer version of the problem. We can actually prove the optimal solution is the same as Monotonic floor/ceil version.

As we assumed, the smallest $v_i$ is 0. Group all the $x_i$'s according to their $v_i$'s, and call them group $0,1,2,...,\max\{v_i\}$. We shall first prove that there are no empty groups, but this is simple, if the $k$-th group is empty, for any $v_i &gt; k$ just let $v_i = v_i-1$. It is easy to see the objective function always improves (basically because $|\{x_i\}-\{x_j\}| &lt; 1$).

Now we shall prove, the average of $\{x_i\}$ in group $k+1$ is at least the average of $\{x_i\}$ in group $k$ plus $1/2$. If this is not true, simply let $v_i = v_i-1$ for all $v_i &gt; k$, computation again shows the objective function improves.

Since the average of $\{x_i\}$ is in range $[0,1)$, there are really at most two groups, which corresponds to the floor/ceil version.