Separating the yes- from the no-instances in the number partitioning problem
Publication date
2024
Document type
Konferenzbeitrag
Author
Organisational unit
Conference
16th International Conference on Evolutionary Computation Theory and Applications (ECTA 2024), part of the 16th International Joint Conference on Computational Intelligence (IJCCI 2024) ; Porto, Portugal ; November 20–22, 2024
Publisher
SciTePress
Book title
Proceedings of the 16th International Joint Conference on Computational Intelligence
Volume (part of multivolume book)
1
First page
181
Last page
188
Part of the university bibliography
✅
Language
English
Abstract
The (two-way) number partitioning problem (NPP) is a well known NP-complete decision problem in which a set of (positive) integers must be split in such a way that the sum of both resulting subsets is equal. However, its optimization problem variant is even harder, since the verification of partitions is only possible in polynomial time for instances which have a perfect partition. We investigate the distribution of instances that have and that do not have a perfect partition, and find that they are not randomly distributed in the instance space. Thus, the hardness of any given instance might be predictable to some extent. We demonstrate that it is possible to separate these two instance types visually using a linear time embedding into R 2 for instances of the same template. Furthermore, we compare three greedy heuristic algorithms (greedy captains, greedy coach, and greedy tyrant) and their difference to the solution from an exact branch-and-bound (BB) algorithm.
Description
License: https://creativecommons.org/licenses/by-nc-nd/4.0/
Version
Published version
Access right on openHSU
Metadata only access