Sum-of-Max Partition under a Knapsack Constraint
share
Sequence partition problems arise in many fields, such as sequential data analysis, information transmission, and parallel computing. In this paper we study the following variant of partition problem: Given a sequence of n items 1,…,n, where each item i is associated with a weight w_i and a parameter s_i, partition the sequence into several consecutive subsequences, so that the total weight of each subsequence is no more than a threshold w_0, and the sum of the largest s_i in each subsequence is minimized. This problem admits a straightforward solution based on dynamic programming, which costs O(n^2) time and can be improved to O(nlog n) time easily. Our main contribution is an O(n) time algorithm, which is nontrivial yet easy to implement. We also study the corresponding tree partition problem. We prove that the problem on tree is NP-complete and we present an O(w_0^2 n^2) time algorithm for the unit weight case.
READ FULL TEXT