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,\ldots,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(n\log 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.
翻译:序列分割问题在许多领域出现, 如相继数据分析、 信息传输和平行计算 。 在本文中, 我们研究分区问题的以下变量 : 鉴于分解问题的顺序为 1美元,\ldots, n$, 每件美元与重量为 $_ i 美元和参数为 $_ i 美元相关, 将序列分成几个连续的子序列, 这样每个子序列的总重量不超过 $w_ 0 美元 的阈值, 而每个子序列中最大的 $_ i 美元的总和被最小化 。 这个问题承认基于动态编程的简单解决方案, 花费 $O (n) 2 美元的时间, 并且可以很容易地改进为 $O (n) 时间。 我们的主要贡献是 $O (n) 时间算法, 它不易执行 。 我们还研究相应的树分区问题 。 我们证明树上的问题是 NP- 完整的, 我们为单位重量案例提出了一个 $O (w_ 0_ 2 n\ 2) 时间算法 。