I've created a diagram that depicts what I'm trying to accomplish.
Diagram
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– Jason2015年04月18日 06:08:02 +00:00Commented Apr 18, 2015 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– vzn2015年04月18日 21:07:00 +00:00Commented Apr 18, 2015 at 21:07
3 Answers 3
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.
-
1$\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– FogleBird2015年04月24日 00:28:29 +00:00Commented Apr 24, 2015 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– FogleBird2015年04月18日 02:17:54 +00:00Commented Apr 18, 2015 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– Yuval Filmus2015年04月18日 03:38:12 +00:00Commented Apr 18, 2015 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– David Richerby2015年04月18日 09:49:02 +00:00Commented Apr 18, 2015 at 9:49