標題: 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
顯示於類別:期刊論文


文件中的檔案:

  1. 000299081200006.pdf

若為 zip 檔案,請下載檔案解壓縮後,用瀏覽器開啟資料夾中的 index.html 瀏覽全文。