<p>Another extended comment... Could be wrong.</p>

<p>I'm also considering the case with floor/ceil restrictions, and I'm trying to solve it using dynamic programming (I can't, but maybe it works when the common divisor is small).</p>

<p>Let $\{x_i\}$ be the fractional part of $x_i$, we consider things from the smallest $\{x_i\}$ to the largest. Suppose the largest is $\{x_k\}$, and because we are doing dynamic programming we already know "something" (I will explain what this something is) about optimal solution for everything else except $x_k$.</p>

<p>Now consider the difference in objective function when we round $x_k$ up or down. If originally some $x_i$ is rounded up, then the difference is simply 1 (haven't really checked very carefully but seems like this is the case, it is really important that no matter whether $x_i$ is to the left or right of $x_k$, the difference is always the same); if originally some $x_i$ is rounded down, then the difference is $2\{x_k\}-2\{x_i\}-1$. So: we know what decision we should make if the following three quantities are known:</p>

<ol>
<li>how many things are rounded up</li>
<li>how many things are rounded down</li>
<li>what is the sum of $\{x_i\}$ among those $x_i$'s that are rounded down</li>
</ol>

<p>OK, 1 and 2 are essentially the same, we can let f[N, Ndown, Sdown] be the optimal solution for the first N points (when the points are sorted in ascending order of $\{x_i\}$), the number of $x_i$'s rounded down is Ndown, and the sum of $\{x_i\}$ for those that are rounded down is Sdown. Then it is not hard to write out how to go from f[N-1] to f[N].</p>

<p>The problem is of course, Sdown can have exponentially many values. But it works when either the common divisor is small, or we can round everything to a grid point first and get a FPTAS (if the above dynamic program is correct...)</p>

CC BY-SA 3.0
2012-08-29T16:25:23.870Z
Just noticed @Marzio De Biasi 's comment. It is much easier to think about this Dynamic programming using that objective function. Since we are essentially sorting according to $D_i$, when we try to consider the final one, all the absolute value disappears. The additional cost is either $\sum D_iv_i$ or $(N-1) D_k - \sum D_iv_i$.
Rong Ge
CC BY-SA 3.0
2012-08-29T16:32:45.733Z
OK $D_i$'s does not have to be positive. But that can also be handled. We only need to tell the difference between $\sum |D_i v_i|$ and $Ndown|D_k| + Nup D_k - \sum D_iv_i$. Ndown is the number of previous $v_j$'s that are equal to 0, Nup is the number of previous $v_j$'s equal to 1.
Rong Ge
CC BY-SA 3.0
2012-08-29T19:18:17.473Z
This looks promising, but I think there are some further difficulties if the input values are too close to each other. Consider e.g. $x_i = 1.1$ and $x_k = 1.9$. Now if we could have $x_i$ rounded up and $x_k$ rounded down, we would no longer have the nice property that the error changes by precisely 1 depending on whether $x_k$ is rounded up or down. On the other hand, if we forbid a rounding that changes the order of the points (as I have in the original question), then it seems that we need to keep track of possible roundings that are still available in the dynamic program; can we do that?
Jukka Suomela
CC BY-SA 3.0
2012-08-30T13:31:39.163Z
@Jukka Suomela, After I saw your comment, I realized that we should never let something with larger $\{x_i\}$ be rounded down while something with smaller $\{x_i\}$ be rounded up. This can be proved if you examine all the cases. Then the answer to the problem (with round restrictions) is clear: there must be a threshold, above the threshold you should round up, below you should round down, at the threshold maybe some should be round up and some down but the quality only depend on the number. These solutions can be easily enumerated.
Rong Ge
CC BY-SA 3.0
2012-08-30T13:34:00.160Z
By examine all the cases I mean, suppose $\{x_i\} < \{x_j\}$, think of another $\{x_k\}$ in one of the three regions split by $\{x_i\}$ and $\{x_j\}$, and $\{x_k\}$ is either rounded up or down. In all of the 6 cases rounding $x_i$ down and $x_j$ up is never worse than rounding $x_j$ down and $x_i$ up.
Rong Ge
CC BY-SA 3.0
2012-08-30T22:26:17.697Z
@RongGe: I didn't think of it too much, but are you sure that if there are many other $\{x_{k1}\},\{x_{k2}\},...$ (and not just one) the minimum error is still obtained rounding $x_i$ down and $x_j$ up ?
Marzio De Biasi
CC BY-SA 3.0
2012-08-30T23:52:41.660Z
@RongGe: This is great! Could you perhaps write a new answer that gives a complete solution for the case of restricted up/down rounding? Perhaps someone can then see how to generalise it...
Jukka Suomela
CC BY-SA 3.0
2012-08-31T03:42:13.700Z
@Marzio De Biasi, yes, because swapping is better (not worse) for all $x_{k_i}$, and the objective function is the sum.
Rong Ge
CC BY-SA 3.0
2012-08-31T03:43:19.177Z
@Jukka Suomela, I think I may actually have a solution for the integer problem (monotonic version), please see the new answer.
Rong Ge
CC BY-SA 3.0
2012-08-29T14:26:04.257Z
2012-08-29T14:26:04.257Z
Rong Ge
<p>Just an extended comment ... (perhaps trivial and/or wrong :)</p>

<p>If $x_i = a_i / b_i$ and $M$ is the least common multiple of the $b_i$s, then we can get rid of the rationals: $x'_i = M*x_i$.</p>

<p>If $y_i \in \{ \lceil x_i \rceil, \lfloor x_i \rfloor \}$ (floor,ceil restriction) then we can use binary variables $v_i$ to express $y'_i$ using its distance from $x'_i$ ($L_i = x'_i - M*\lfloor x_i \rfloor$ or $R_i = x'_i - M*\lceil x_i \rceil$):</p>

<p>$y'_i = x'_i + L_i * v_i + R_i * (1 - v_i) = x'_i + (L_i - R_i)*v_i + R_i = x'_i + D_i *v_i + R_i$</p>

<p>And the original problem should (?!?) be equivalent to finding the $v_i$ that minimize:</p>

<p>$\sum_{1 \le i &lt; j \leq n} | D_i * v_i - D_j * v_j |$</p>

<p>with $v_i \in \{0,1\}, D_i \in \mathbb{Z}$</p>

CC BY-SA 3.0
2012-08-29T15:38:25.953Z
expanding your last summation using the $e'(i,j)$ error fn idea above, could it be shown the optimum is actually just the choice where each binary variable floor/ceil is closer to $x_n$? so that leaves only the case of how to round for $x_n$ in the form $m_n + {1 \over 2}$ where $m$ is an integer.
vzn
CC BY-SA 3.0
2012-08-29T16:16:03.010Z
@vzn: I think this is a counterexample. If we round $(0, 1.4, 8.7)$ using rounding $x_i$ criteria we get $(0, 1, 9)$ that has an error of $1.4$, but $(0,2,9)$ has an error of $1.2$ (the result is the same if we eliminate the rationals multiplying by the LCM).
Marzio De Biasi
CC BY-SA 3.0
2012-08-29T17:51:52.717Z
ok nevertheless new idea. consider $e'(i,j)$ again. expand the summation. it will reduce to many terms with $v_i$ and also $v_i^2$. but the latter is equal to $v_i$! therefore it reduces to a problem in the form of minimizing $X*D$ where $X$ is a 0/1 _row vector_ and $D$ is a _constant column vector_. true?  then that is trivial, and just select the $X$ such that it is 1 if the corresponding element in $D$ is negative and 0 if it is positive.... QED?
vzn
CC BY-SA 3.0
2012-08-29T18:02:51.797Z
@vzn: if you use the $((y'_i - y'_j) - (x'_i - x'_j))^2$ error to eliminate the absolute value function, then you get terms like $- 2*D_i * D_j * v_i * v_j$; how do you handle them in the minimization?
Marzio De Biasi
CC BY-SA 3.0
2012-08-29T18:25:18.493Z
oops! you answered before I had a chance to delete that comment after realizing that.. anyway it still seems to reduce to some almost linear matrix optimization problem? also with a term $V * V^T$ where $V$ is a column vector...?
vzn
CC BY-SA 3.0
2012-08-29T13:31:51.953Z
2012-08-29T13:31:51.953Z
Marzio De Biasi
<p>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).</p>

<p>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). </p>

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

<p>$$
||v_i-v_j+ \lfloor x_i\rfloor -  \lfloor x_j\rfloor| - |\{x_i\}-\{x_j\} + \lfloor x_i\rfloor - \lfloor x_j\rfloor||
$$</p>

<p>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</p>

<p>$$
|v_i-v_j - (\{x_i\} - \{x_j\})|
$$</p>

<p>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)</p>

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

<p>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.</p>

<p>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.</p>

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

<p>$|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\})|$.</p>

<p>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.</p>

<p>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).</p>

<p>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.</p>

<p>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$).</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2012-08-31T03:40:49.990Z
2012-08-31T03:40:49.990Z
Rong Ge
<p>What is known about the complexity of the following problem:</p>

<ul>
<li>Given: rational numbers $x_1 &lt; x_2 &lt; \dotso &lt; x_n$.</li>
<li>Output: integers $y_1 \le y_2 \le \dotso \le y_n$.</li>
<li>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)|.$$</li>
</ul>

<p>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$.</p>

<hr>

<p>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$.</p>

<p><img src="https://i.sstatic.net/fWVwn.png" alt="route map"></p>

<p><a href="http://www.hsl.fi/EN/timetablesandroutes/maps/Pages/Metro.aspx" rel="nofollow noreferrer">(source)</a></p>

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

<ul>
<li>A–B ≈ 1 minute, B–C ≈ 2 minutes, C–D ≈ 2 minutes</li>
<li>A–C ≈ 3 minutes, B–D ≈ 4 minutes</li>
<li>A–D ≈ 5 minutes</li>
</ul>

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

<hr>

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

<p>Does anyone recognise this problem? Or see a clever algorithm for solving it?</p>

<hr>

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

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

<p>The original question considers the monotonic integer version, but answers related to any of these versions are welcome.</p>

CC BY-SA 3.0
2012-08-14T09:11:48.343Z
Does the DP work for the case when you only care about adjacent measurements ?
Suresh Venkat
CC BY-SA 3.0
2012-08-14T12:36:33.797Z
@SureshVenkat: Actually, in that case the problem becomes very simple: you just select the best integral distance $y_i - y_{i-1}$ for each $i$. That is, you can minimise each $e(i-1,i)$ independently.
Jukka Suomela
CC BY-SA 3.0
2012-08-14T18:16:19.523Z
This report by Estie Arkin seems related:
http://www.ams.sunysb.edu/~estie/papers/beautification.pdf 
It is proved that minimizing the number of distinct inter-point distances in the output is NP-hard. This is not the total sum of shifts, as in this questions, but maybe the hardness gadgets in the report could suggest a hardness proof for this problem.
val
CC BY-SA 3.0
2012-08-14T23:07:17.597Z
Is it essential to require that the order is preserved?  In other words, is there an instance where dropping the constraint y_1 ≤ y_2 ≤ … ≤ y_n changes the optimal value?  Not that I know the answer for the problem with this constraint dropped, but I just wonder if you can potentially simplify the problem by dropping it.
Tsuyoshi Ito
CC BY-SA 3.0
2012-08-14T23:18:45.790Z
@TsuyoshiIto: Good question. For the "real" application, I guess we would prefer a solution with $y_1 < y_2 < \dotso < y_n$, and this additional constraint certainly changes the optimum. The formulation with $\le$ was just a simplification — my intuition was that dropping the $\le$ constraint "obviously" never helps, but I have not actually checked it yet.
Jukka Suomela
CC BY-SA 3.0
2012-08-26T22:41:26.137Z
I have a feeling that this problem should certainly be solvable using well-known techniques. Let's see if the bounty is enough to motivate people to solve this. :)
Jukka Suomela
CC BY-SA 3.0
2012-08-28T16:30:31.847Z
what about this as a possible simplification or constraint-- the optimum must round every rational either using floor(x) or ceil(x)? then there are 2^n possible cases to consider...? moreover much of the math in the 2^n comparisons (calculation of the error function for each case) is repeated & can be reused...
vzn
CC BY-SA 3.0
2012-08-28T17:46:54.377Z
re the Estie ref cited by val above.. somewhat similar however note it considers ("1d beautification as NP complete", p2) _adjacent_ point differences $y_{i+1} - y_i$ -- not pairwise. a nice analysis might relate the adjacent and pairwise problems, its not clear theres any relation so far...
vzn
CC BY-SA 3.0
2012-08-28T18:15:45.530Z
further idea-- use $e'(i,j) = ((y_j - y_i) - (x_j - x_i))^2$ instead of absolute value to minimize. this often improves the algebraic analyzability/simplification of many probs & often does not affect the minimum
vzn
CC BY-SA 3.0
2012-08-28T22:06:38.317Z
using the floor/ceil idea, think there is a fast greedy algorithm that finds a pretty good local optimum using an approach similar to powells algorithm. it seems like in this formulation the search space is "mostly concave"... but maybe you are not actually interested in a numerical solution?
vzn
CC BY-SA 3.0
2012-08-28T23:12:20.290Z
@vzn: I am interested in the computational complexity of this problem. If you can prove that there is a polynomial-time local search approach that is *guaranteed* to find the global optimum, the bounty is yours.
Jukka Suomela
<ds.algorithms><reference-request><optimization>
Rounding to minimise the sum of errors in pairwise distances
Jukka Suomela
# Rounding to minimise the sum of errors in pairwise distances

(Asked by: username_0 on 2012-08-13)

What is known about the complexity of the following problem:

* Given: rational numbers $x\_1 < x\_2 < \dotso < x\_n$.
* Output: integers $y\_1 \le y\_2 \le \dotso \le y\_n$.
* Objective: minimise $$\sum\_{1 \le i < 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

![route map](https://i.sstatic.net/fWVwn.png)

[(source)](http://www.hsl.fi/EN/timetablesandroutes/maps/Pages/Metro.aspx)

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 > y\_j$ for $i < j$.

The original question considers the monotonic integer version, but answers related to any of these versions are welcome.

**Tags:** ds.algorithms, reference-request, optimization
> **Comments:**
> **username_1**: Does the DP work for the case when you only care about adjacent measurements ?  
> **username_0**: @SureshVenkat: Actually, in that case the problem becomes very simple: you just select the best integral distance $y_i - y_{i-1}$ for each $i$. That is, you can minimise each $e(i-1,i)$ independently.  
> **username_2**: This report by Estie Arkin seems related: http://www.ams.sunysb.edu/~estie/papers/beautification.pdf  It is proved that minimizing the number of distinct inter-point distances in the output is NP-hard. This is not the total sum of shifts, as in this questions, but maybe the hardness gadgets in the report could suggest a hardness proof for this problem.  
> **username_3**: Is it essential to require that the order is preserved?  In other words, is there an instance where dropping the constraint y_1 ≤ y_2 ≤ … ≤ y_n changes the optimal value?  Not that I know the answer for the problem with this constraint dropped, but I just wonder if you can potentially simplify the problem by dropping it.  
> **username_0**: @TsuyoshiIto: Good question. For the "real" application, I guess we would prefer a solution with $y_1 < y_2 < \dotso < y_n$, and this additional constraint certainly changes the optimum. The formulation with $\le$ was just a simplification — my intuition was that dropping the $\le$ constraint "obviously" never helps, but I have not actually checked it yet.  
> **username_0**: I have a feeling that this problem should certainly be solvable using well-known techniques. Let's see if the bounty is enough to motivate people to solve this. :)  
> **username_4**: what about this as a possible simplification or constraint-- the optimum must round every rational either using floor(x) or ceil(x)? then there are 2^n possible cases to consider...? moreover much of the math in the 2^n comparisons (calculation of the error function for each case) is repeated & can be reused...  
> **username_4**: re the Estie ref cited by val above.. somewhat similar however note it considers ("1d beautification as NP complete", p2) _adjacent_ point differences $y_{i+1} - y_i$ -- not pairwise. a nice analysis might relate the adjacent and pairwise problems, its not clear theres any relation so far...  
> **username_4**: further idea-- use $e'(i,j) = ((y_j - y_i) - (x_j - x_i))^2$ instead of absolute value to minimize. this often improves the algebraic analyzability/simplification of many probs & often does not affect the minimum  
> **username_4**: using the floor/ceil idea, think there is a fast greedy algorithm that finds a pretty good local optimum using an approach similar to powells algorithm. it seems like in this formulation the search space is "mostly concave"... but maybe you are not actually interested in a numerical solution?  
> **username_0**: @vzn: I am interested in the computational complexity of this problem. If you can prove that there is a polynomial-time local search approach that is *guaranteed* to find the global optimum, the bounty is yours.  

---

## 3 answers

### Answer by username_5 on 2012-08-31. Score: 9 | Accepted answer

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\} > \{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\} > \{x\_j\}$ but $v\_i < 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 > k$ just let $v\_i = v\_i-1$. It is easy to see the objective function always improves (basically because $|\{x\_i\}-\{x\_j\}| < 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 > 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.


---

### Answer by username_5 on 2012-08-29. Score: 1

Another extended comment... Could be wrong.

I'm also considering the case with floor/ceil restrictions, and I'm trying to solve it using dynamic programming (I can't, but maybe it works when the common divisor is small).

Let $\{x\_i\}$ be the fractional part of $x\_i$, we consider things from the smallest $\{x\_i\}$ to the largest. Suppose the largest is $\{x\_k\}$, and because we are doing dynamic programming we already know "something" (I will explain what this something is) about optimal solution for everything else except $x\_k$.

Now consider the difference in objective function when we round $x\_k$ up or down. If originally some $x\_i$ is rounded up, then the difference is simply 1 (haven't really checked very carefully but seems like this is the case, it is really important that no matter whether $x\_i$ is to the left or right of $x\_k$, the difference is always the same); if originally some $x\_i$ is rounded down, then the difference is $2\{x\_k\}-2\{x\_i\}-1$. So: we know what decision we should make if the following three quantities are known:

1. how many things are rounded up
2. how many things are rounded down
3. what is the sum of $\{x\_i\}$ among those $x\_i$'s that are rounded down

OK, 1 and 2 are essentially the same, we can let f[N, Ndown, Sdown] be the optimal solution for the first N points (when the points are sorted in ascending order of $\{x\_i\}$), the number of $x\_i$'s rounded down is Ndown, and the sum of $\{x\_i\}$ for those that are rounded down is Sdown. Then it is not hard to write out how to go from f[N-1] to f[N].

The problem is of course, Sdown can have exponentially many values. But it works when either the common divisor is small, or we can round everything to a grid point first and get a FPTAS (if the above dynamic program is correct...)

> **Comments:**
> **username_5**: Just noticed @Marzio De Biasi 's comment. It is much easier to think about this Dynamic programming using that objective function. Since we are essentially sorting according to $D_i$, when we try to consider the final one, all the absolute value disappears. The additional cost is either $\sum D_iv_i$ or $(N-1) D_k - \sum D_iv_i$.  
> **username_5**: OK $D_i$'s does not have to be positive. But that can also be handled. We only need to tell the difference between $\sum |D_i v_i|$ and $Ndown|D_k| + Nup D_k - \sum D_iv_i$. Ndown is the number of previous $v_j$'s that are equal to 0, Nup is the number of previous $v_j$'s equal to 1.  
> **username_0**: This looks promising, but I think there are some further difficulties if the input values are too close to each other. Consider e.g. $x_i = 1.1$ and $x_k = 1.9$. Now if we could have $x_i$ rounded up and $x_k$ rounded down, we would no longer have the nice property that the error changes by precisely 1 depending on whether $x_k$ is rounded up or down. On the other hand, if we forbid a rounding that changes the order of the points (as I have in the original question), then it seems that we need to keep track of possible roundings that are still available in the dynamic program; can we do that?  
> **username_5**: @Jukka Suomela, After I saw your comment, I realized that we should never let something with larger $\{x_i\}$ be rounded down while something with smaller $\{x_i\}$ be rounded up. This can be proved if you examine all the cases. Then the answer to the problem (with round restrictions) is clear: there must be a threshold, above the threshold you should round up, below you should round down, at the threshold maybe some should be round up and some down but the quality only depend on the number. These solutions can be easily enumerated.  
> **username_5**: By examine all the cases I mean, suppose $\{x_i\} < \{x_j\}$, think of another $\{x_k\}$ in one of the three regions split by $\{x_i\}$ and $\{x_j\}$, and $\{x_k\}$ is either rounded up or down. In all of the 6 cases rounding $x_i$ down and $x_j$ up is never worse than rounding $x_j$ down and $x_i$ up.  
> **username_6**: @RongGe: I didn't think of it too much, but are you sure that if there are many other $\{x_{k1}\},\{x_{k2}\},...$ (and not just one) the minimum error is still obtained rounding $x_i$ down and $x_j$ up ?  
> **username_0**: @RongGe: This is great! Could you perhaps write a new answer that gives a complete solution for the case of restricted up/down rounding? Perhaps someone can then see how to generalise it...  
> **username_5**: @Marzio De Biasi, yes, because swapping is better (not worse) for all $x_{k_i}$, and the objective function is the sum.  
> **username_5**: @Jukka Suomela, I think I may actually have a solution for the integer problem (monotonic version), please see the new answer.  

---

### Answer by username_6 on 2012-08-29. Score: 1

Just an extended comment ... (perhaps trivial and/or wrong :)

If $x\_i = a\_i / b\_i$ and $M$ is the least common multiple of the $b\_i$s, then we can get rid of the rationals: $x'\_i = M\*x\_i$.

If $y\_i \in \{ \lceil x\_i \rceil, \lfloor x\_i \rfloor \}$ (floor,ceil restriction) then we can use binary variables $v\_i$ to express $y'\_i$ using its distance from $x'\_i$ ($L\_i = x'\_i - M\*\lfloor x\_i \rfloor$ or $R\_i = x'\_i - M\*\lceil x\_i \rceil$):

$y'\_i = x'\_i + L\_i \* v\_i + R\_i \* (1 - v\_i) = x'\_i + (L\_i - R\_i)\*v\_i + R\_i = x'\_i + D\_i \*v\_i + R\_i$

And the original problem should (?!?) be equivalent to finding the $v\_i$ that minimize:

$\sum\_{1 \le i < j \leq n} | D\_i \* v\_i - D\_j \* v\_j |$

with $v\_i \in \{0,1\}, D\_i \in \mathbb{Z}$

> **Comments:**
> **username_4**: expanding your last summation using the $e'(i,j)$ error fn idea above, could it be shown the optimum is actually just the choice where each binary variable floor/ceil is closer to $x_n$? so that leaves only the case of how to round for $x_n$ in the form $m_n + {1 \over 2}$ where $m$ is an integer.  
> **username_6**: @vzn: I think this is a counterexample. If we round $(0, 1.4, 8.7)$ using rounding $x_i$ criteria we get $(0, 1, 9)$ that has an error of $1.4$, but $(0,2,9)$ has an error of $1.2$ (the result is the same if we eliminate the rationals multiplying by the LCM).  
> **username_4**: ok nevertheless new idea. consider $e'(i,j)$ again. expand the summation. it will reduce to many terms with $v_i$ and also $v_i^2$. but the latter is equal to $v_i$! therefore it reduces to a problem in the form of minimizing $X*D$ where $X$ is a 0/1 _row vector_ and $D$ is a _constant column vector_. true?  then that is trivial, and just select the $X$ such that it is 1 if the corresponding element in $D$ is negative and 0 if it is positive.... QED?  
> **username_6**: @vzn: if you use the $((y'_i - y'_j) - (x'_i - x'_j))^2$ error to eliminate the absolute value function, then you get terms like $- 2*D_i * D_j * v_i * v_j$; how do you handle them in the minimization?  
> **username_4**: oops! you answered before I had a chance to delete that comment after realizing that.. anyway it still seems to reduce to some almost linear matrix optimization problem? also with a term $V * V^T$ where $V$ is a column vector...?  

---

