Sum-of-Max partition under a Knapsack constraint. (January 2023)

• Record Type: Journal Article
• Authors: Jin, Kai; Zhang, Danna; Zhang, Canhui
• Is Part Of: Computers & electrical engineering. Volume 105(2023)
• Publication Date: 2023-01
• Subjects: Sequence partition -- Tree partition -- Dynamic programming speed up -- Options dividing technique -- Monotonic queue; Computer engineering -- Periodicals; Electrical engineering -- Periodicals; Electrical engineering -- Data processing -- Periodicals; Ordinateurs -- Conception et construction -- Périodiques; Électrotechnique -- Périodiques; Électrotechnique -- Informatique -- Périodiques; Computer engineering; Electrical engineering; Electrical engineering -- Data processing; Periodicals; Electronic journals; 621.302854
• DOI: 10.1016/j.compeleceng.2022.108521
• Languages: English
• ISSNs: 0045-7906

Abstract

Abstract: Sequence partition problems arise in many fields, such as sequential data analysis, information transmission, and parallel computing. In this paper, we study the following partition problem variant: given a sequence of n items 1, …, n, where each item i is associated with weight w i and another 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 ( n log n ) time easily. Our 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 the tree is NP-complete and we present an O ( w 0 n 2 ) time ( O ( w 0 2 n 2 ) time, respectively) algorithm for the unit weight (integer weight, respectively) case.