Algoritmo eficiente para esse problema de otimização? Programaçao dinamica?

Eu criei um diagrama que mostra o que estou tentando realizar.

Imagem em tamanho real

Na sequência de entrada, os nós estão o mais próximos possível. Mas eu quero que os nós brancos estejam o mais próximo possível dos respectivos nós pretos. As arestas entre os nós podem ser alongadas para tentar minimizar esse erro. Eles não podem ser encurtados. Portanto, 1 -> 2pode ser não menos que 4, por exemplo.

Eu incluí uma solução possível. As arestas que foram alongadas são rotuladas. Observe que o alongamento de uma aresta muda todos os nós para a direita.

Esse eixo é contínuo, mas eu poderia discretizá-lo se isso ajudar.

Estou pensando que uma abordagem de programação dinâmica poderia funcionar aqui, mas não tenho certeza - nunca fui muito bom com o DP.

Qual é o algoritmo de execução mais rápida que pode resolver isso? Isso pode ser categorizado / reformulado como um problema conhecido?

Esta é apenas uma extensão da resposta de @ Sébastien Loisel.

Observe minimizar $(x_i-y_i)^2$ sujeito a $x_i-x_{i-1}\ge c_i$ é equivalente a minimizar $(x_i-(y_i-c_i))^2$ sujeito a $x_i\geq x_{i-1}$. Deixei$a_i=y_i-c_i$, esse é precisamente o problema de regressão isotônica . Existe um$O(n)$ algoritmo de tempo.

Se você discretizar o eixo, poderá usar a programação dinâmica. Para cada bola$b$ e localização viável $\ell$ (dentro de alguns limites razoáveis), calcule o melhor erro quadrático médio para o primeiro $b$bolas. Isso pode ser feito geralmente apenas o mesmo tipo de informação para bola$b-1$.

Este é um programa quadrático. Você está tentando minimizar a soma de$(x_i-y_i)^2$ sujeito a $x_i-x_{i-1}\ge c_i$.