25
$\begingroup$

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<j$.

route map

(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 > y_j$ for $i < j$.

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

$\endgroup$
  • $\begingroup$ Does the DP work for the case when you only care about adjacent measurements ? $\endgroup$ – Suresh Venkat Aug 14 '12 at 9:11
  • 1
    $\begingroup$ @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. $\endgroup$ – Jukka Suomela Aug 14 '12 at 12:36
  • 4
    $\begingroup$ This report by Estie Arkin seems related: 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. $\endgroup$ – val Aug 14 '12 at 18:16
  • 2
    $\begingroup$ 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. :) $\endgroup$ – Jukka Suomela Aug 26 '12 at 22:41
  • 1
    $\begingroup$ @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. $\endgroup$ – Jukka Suomela Aug 28 '12 at 23:12
9
+500
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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}$

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – vzn Aug 29 '12 at 15:38
  • 1
    $\begingroup$ @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). $\endgroup$ – Marzio De Biasi Aug 29 '12 at 16:16
  • $\begingroup$ 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? $\endgroup$ – vzn Aug 29 '12 at 17:51
  • 1
    $\begingroup$ @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? $\endgroup$ – Marzio De Biasi Aug 29 '12 at 18:02
  • $\begingroup$ 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...? $\endgroup$ – vzn Aug 29 '12 at 18:25
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Rong Ge Aug 29 '12 at 16:25
  • $\begingroup$ 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. $\endgroup$ – Rong Ge Aug 29 '12 at 16:32
  • $\begingroup$ 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? $\endgroup$ – Jukka Suomela Aug 29 '12 at 19:18
  • 1
    $\begingroup$ @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. $\endgroup$ – Rong Ge Aug 30 '12 at 13:31
  • 1
    $\begingroup$ 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. $\endgroup$ – Rong Ge Aug 30 '12 at 13:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.