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?
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_igeq 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
