A new approach to solve open-partition problems |
| |
Authors: | Huilan Chang Frank K Hwang Uriel G Rothblum |
| |
Institution: | 1. Department of Applied Mathematics, National Chiao Tung University, Hsinchu, 30010, Taiwan, ROC 2. DIMACS, Rutgers University, 96 Frelinghuysen Road, Piscataway, NJ, 08854, USA 3. 6306 Westover Way, Somerset, NJ, 08873, USA 4. Faculty of Industrial Engineering and Management, Technion, Haifa, 32000, Israel
|
| |
Abstract: | 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|