Article ID: | iaor2012238 |
Volume: | 23 |
Issue: | 1 |
Start Page Number: | 61 |
End Page Number: | 78 |
Publication Date: | Jan 2012 |
Journal: | Journal of Combinatorial Optimization |
Authors: | Hwang Frank, Chang Huilan, Rothblum Uriel |
Keywords: | combinatorial optimization |
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.