A new approach to solve open-partition problems

作者：Chang Huilan^*; Hwang Frank K; Rothblum Uriel G

来源：Journal of Combinatorial Optimization, 2012, 23(1): 61-78.

DOI：10.1007/s10878-010-9341-7

• Partition
• Objective function
• Partition property
• Sortability

A partition problem in one-dimensional space is to seek a partition of a set of numbers that maximizes a given objective function. In some partition problems, the partition size, i.e., the number of nonempty parts in a partition, is fixed; while in others, the size can vary arbitrarily. We call the former the size-partition problem and the latter the open-partition problem. In general, it is much harder to solve open problems since the objective functions depend on size. In this paper, we propose a new approach by allowing empty parts and transform the open problem into a size problem allowing empty parts, called a relaxed-size problem. While the sortability theory has been established in the literature as a powerful tool to attack size partition problems, we develop the sortability theory for relaxed-size problems as a medium to solve open problems.

• 出版日期2012-1