I've created a diagram that depicts what I'm trying to accomplish.


Full-size Image

In the input sequence, the nodes are as close together as possible. But I want the white nodes to be as close to their respective black nodes as possible. The edges between nodes can be lengthened to try to minimize this error. They cannot be shortened. So, 1 -> 2 can be no less than 4, for example.

I've included a possible solution. The edges that have been lengthened are labeled. Note that lengthening an edge shifts all the nodes to its right.

This axis is continuous, but I could possibly discretize it if that helps.

I'm thinking a dynamic programming approach could work here but I'm not sure - I was never very good with DP.

What's the fastest running algorithm that can solve this? Can this be categorized / re-framed as a well-known problem?

  • $\begingroup$ To solve this with DP, just think about the structure/sub-structure of the solution and solve from the bottom up. That should give a linear run-time. I think it's also generally solvable as a system of linear equations, but solving/optimizing may have not have better run-time. $\endgroup$ – Jason Apr 18 '15 at 6:08
  • 1
    $\begingroup$ plz do not put key details written in the image text. also you havent actually formally described the problem (in math terms), thats half the battle. "minimize mean squared error" of what? however it looks like a 1d version of the "facilities location problem" $\endgroup$ – vzn Apr 18 '15 at 21:07

This is just an extension to @Sébastien Loisel's answer.

Notice minimize $(x_i-y_i)^2$ subject to $x_i-x_{i-1}\ge c_i$ is equivalent to minimize $(x_i-(y_i-c_i))^2$ subject to $x_i\geq x_{i-1}$. Let $a_i=y_i-c_i$, then this is precisely the isotonic regression problem. There exist a $O(n)$ time algorithm.

  • $\begingroup$ Excellent - I implemented an isotonic regression (pool adjacent violators algorithm) and it's working perfectly and much faster than my memoized search algorithm. Thanks! $\endgroup$ – FogleBird Apr 24 '15 at 0:28

If you discretize the axis then you can use dynamic programming. For each ball $b$ and feasible location $\ell$ (within some reasonable bounds), calculate the best mean squared error for the first $b$ balls. This can be done usually only the same kind of information for ball $b-1$.

  • $\begingroup$ Can you take a look at the code I wrote and tell me how a DP approach might differ performance-wise? $\endgroup$ – FogleBird Apr 18 '15 at 2:17
  • $\begingroup$ If your approach works for you, great. Can you estimate its complexity? Can you estimate the complexity of my suggestion? That can help you decide whether it's worth it to program my approach. If you decide that it's worth it, you can compare the two approaches empirically. Which approach works better also depends on the size and nature of the inputs – make sure that you test your approach on actual inputs. $\endgroup$ – Yuval Filmus Apr 18 '15 at 3:38

This is a quadratic program. You are trying to minimise the sum of $(x_i-y_i)^2$ subject to $x_i-x_{i-1}\ge c_i$.

  • $\begingroup$ This answers "Can this be categorized / re-framed as a well-known problem?" but it would be nice to givesome more detail. $\endgroup$ – David Richerby Apr 18 '15 at 9:49

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.