faster algorithms for minimum maximum contiguous k partition

Question

I was reading this http://www.cas.mcmaster.ca/~terlaky/4-6TD3/slides/DP/DP.pdf and would like to know if there exists a solution with better time complexity to the partition problem.

From the link:

"Suppose a given arrangement S of non-negative numbers {s1,...,sn} and an integer k. How to cut S into k or fewer ranges, so as to minimize the maximum sum over all the ranges?"

e.g.

S = 1,2,3,4,5,6,7,8,9

k=3

By cutting S into these 3 ranges, the sum of the maximum range (8,9) is 17, which is the minimum possible.

1,2,3,4,5|6,7|8,9

The algorithm suggested in the link runs in O(kn^2) and uses O(kn) space. Are there more efficient algorithms?

This is a dynamic programming problem. Rather than running in exponential time it optimizes the solution to be in only polynomial time. This is very good, so I don't think you have to search for a "more efficient" solution — user586399
– user586399, Commented Feb 2, 2013 at 7:13

William Rookwood · Accepted Answer · 2013-02-07 07:21:21Z

1

Ok so apparently this was closed for being "off-topic"!? But it's back up now so anyway, I found the solution to be binary searching the answer. Sorry I forgot one of the constraints was that the sum of all the integers would not exceed 2^64. So let C = cumulative sum of all integers. Then we can binary search for the answer using a

bool isPossible(int x)

function which returns true if it is possible to divide S into k partitions with maximum partition sum less than X. isPossible(int x) can be done in O(n) (by adding everything from left to right and if it exceeds x make a new partition). So the total running time is O(n*log(s)).

answered Feb 7, 2013 at 7:21

William Rookwood

3274 silver badges15 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

faster algorithms for minimum maximum contiguous k partition

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related