A new approach to solve open‐partition problems

A new approach to solve open‐partition problems

0.00 Avg rating0 Votes
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: , ,
Keywords: combinatorial optimization
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.

Reviews

Required fields are marked *. Your email address will not be published.