I've created a diagram that depicts what I'm trying to accomplish.Full-size ImageIn 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?
Efficient algorithm for this optimization problem? Dynamic programming?
algorithms;dynamic programming
This is just an extension to @Sbastien 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.