Efficient algorithm for this optimization problem? Dynamic programming?

Problem Detail: 

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?

Asked By : FogleBird

Answered By : Chao Xu

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/41519