Proof of optimality of algorithm

[Sebastian Martinez]

Homework Statement

Given an array of positive integers A[1, . . . , n], and an integer M > 0, you want to partition the array into segments A[1, . . . , i1], A[i_1 + 1, . . . , i2], . . . , A[i_k−1 + 1, . . . , ik], so that the sum of integers in every segment does not exceed M, while minimizing the number of segments k. You can assume that M ≥ A for all i (which guarantees that such a partition exists). Design an O(n) greedy algorithm for solving this problem and prove that it is optimal (i.e. that the obtained partition has the smallest possible number of segments).

Homework Equations

The Attempt at a Solution

The algorithm is very easy just keep adding the values in the array until you see that the sum is greater than M, then start a new segment.

How can I prove that it's optimal?

 

[andrewkirk]

How can I prove that it's optimal?

Try using induction on the number of segments m found by the algorithm. The base case where m=1 is trivial, as it's not possible to have fewer than one segment, provided n>0.
Then try to prove that, if the algorithm produces a partition with the minimum number of segments whenever it comes up with an m-segment partition, it will also do so when it comes up with an m+1 segment partition.

 

[Sebastian Martinez]

Try using induction on the number of segments m found by the algorithm. The base case where m=1 is trivial, as it's not possible to have fewer than one segment, provided n>0.
Then try to prove that, if the algorithm produces a partition with the minimum number of segments whenever it comes up with an m-segment partition, it will also do so when it comes up with an m+1 segment partition.

So we can prove the m+1 by expanding the array with k elements in a way that their sum is less than M?

 

[andrewkirk]

Think about the partition the algorithm has produced with m+1 segments. What can we say about the sub-partition consisting of the first m segments, compared to any other possible partition of that part of the array?

 

[Sebastian Martinez]

Think about the partition the algorithm has produced with m+1 segments. What can we say about the sub-partition consisting of the first m segments, compared to any other possible partition of that part of the array?

it has the least number of segments in that part of the array

 

[andrewkirk]

On reflection I think that induction hypothesis may be harder than necessary. An easier one to prove, because it's more closely aligned with how the algorithm works, is the proposition P(n), which says that, when the algorithm completes the n-th segment, there is no other n-segment partition that can hold a greater number of consecutive elements (starting with the first element) than the one the algorithm has created.

P(1) is very easy to prove, and proving P(m+1) from P(m) is also fairly easy. Having proven that, it's then only a few steps to show that if the algorithm divides the array into m segments, no other partition can divide it into only m-1 segments.

 

[John Roberts]

Yo are you in Manfred's algorithm class too?

 

[rcgldr]

I'm not sure about adding values in the array in order, consider the case for M = 9, A[8] = {1 2 3 4 5 6 7 8}

Scanning in order results in 5 segments:

{1 2 3} {4 5} { 6} {7} {8}

but 4 segments are possible.

{1 8} {2 7} {3 6} {4 5}

I'm wondering if there are cases where taking values from near the start, near the middle, and near the end is needed. Seems that the basic idea is to have the sum of each segment close to or equal to M, or to minimize the sum of the k instances of {M - sum of each segment}.

 

[andrewkirk]

Scanning in order results in 5 segments:

{1 2 3} {4 5} { 6} {7} {8}

but 4 segments are possible.

{1 8} {2 7} {3 6} {4 5}

It is not made clear in the OP, but I took it that the elements of the array are sorted in ascending order (they may even be consecutive integers), and they have to retain their order in the partition, both within and between segments. So the above partition into four segments is not permissible - it preserves order within but not between segments.
The reason I interpreted it that way is that I'm pretty sure no O(n) algorithm can work otherwise, because a sort would be needed to find the optimal partition, and sorting is O(n^2). In addition, the use of the word 'segment' suggests that the only disturbance allowed is making a cut. If rearranging were allowed, I think the word 'subset' would have been used instead.
The process of creating the partition can be thought of as putting dividers into the array between selected elements, without disturbing the order.

 

[rcgldr]

I took it that the elements of the array are sorted in ascending order (they may even be consecutive integers), and they have to retain their order in the partition, both within and between segments.

Your interpretation is how the statement reads, but it seems too simple to be the intended problem.