標題: | A new approach to solve open-partition problems |
作者: | Chang, Huilan Hwang, Frank K. Rothblum, Uriel G. 應用數學系 Department of Applied Mathematics |
關鍵字: | Partition;Objective function;Partition property;Sortability |
公開日期: | 1-一月-2012 |
摘要: | 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. |
URI: | http://dx.doi.org/10.1007/s10878-010-9341-7 http://hdl.handle.net/11536/15312 |
ISSN: | 1382-6905 |
DOI: | 10.1007/s10878-010-9341-7 |
期刊: | JOURNAL OF COMBINATORIAL OPTIMIZATION |
Volume: | 23 |
Issue: | 1 |
起始頁: | 61 |
結束頁: | 78 |
顯示於類別: | 期刊論文 |