[Mgccl]

Since I'm a CS theory person, I can offer some theoretical improvements on the running time and make the problem even more general...

Instead of minimize the linear difference of partition, we might want to minimize the standard deviation, or basically any convex function, and still do it in the same time bound.

One can reduce this problem to find a k-edge path of minimum weight on a complete DAG. The naive algorithm will run in O(kn^2), but we can improve the running time to O(kn) by realize the weight on this DAG has the Monge property. This is very practical to implement.

I posed it as a problem on daily haskell exercise http://dailyhaskellexercise.tumblr.com/post/58060450750/the-....

In this application, k is very large. n is just a constant multiple of k. We can use a theoretically better algorithm that takes n2^O(sqrt(log n loglog n)) time. (this is almost O(n^(3/2))). I doubt it will ever be implemented with speed comparible to the O(kn) solution. See http://www.cs.ust.hk/mjg_lib/bibs/DPSu/DPSu.Files/sdarticle_...

I shall post a solution tomorrow since I'm currently touring NYC with my gf...

[anonymoushn]

What is a complete DAG? Can I create one by just taking a complete graph, choosing an arbitrary ordering of the vertices, and assigning each edge a direction according to that ordering?

Edit: after reading the problem statement, yes, I can.

[jongleberry]

a solution would be awesome, especially in javascript. i actually found a case where their linear algorithm, https://github.com/crispymtn/linear-partition, failed.

[Mgccl]

See the updated content in the link and the code in here http://www.chaoxuprime.com/posts/2013-08-16-more-algorithms-... Both in Haskell. you can see how to implement it from scratch...