Separating the Yes- from the No-Instances in the Number Partitioning Problem

Ruben Horn, Reitze Jansen, Okke van Eck, Daan van Den Berg

Research output: Chapter in Book / Report / Conference proceedingConference contributionAcademicpeer-review

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.

Original languageEnglish
Title of host publicationIJCCI 2024 - Proceedings of the 16th International Joint Conference on Computational Intelligence - ECTA, Porto, Portugal, November 20-22, 2024
Subtitle of host publicationVolume 1
EditorsFrancesco Marcelloni, Kurosh Madani, Niki van Stein, Joaquim Joaquim
PublisherSciTePress
Pages181-188
Number of pages8
Volume1
ISBN (Print)9789897587214
DOIs
Publication statusPublished - 2024
Event16th International Joint Conference on Computational Intelligence, IJCCI 2024 - Porto, Portugal
Duration: 20 Nov 202422 Nov 2024

Conference

Conference16th International Joint Conference on Computational Intelligence, IJCCI 2024
Country/TerritoryPortugal
CityPorto
Period20/11/2422/11/24

Bibliographical note

Online published: 2025-01-15.

Publisher Copyright:
© 2024 by Paper published under CC license (CC BY-NC-ND 4.0)

Keywords

  • Branch-and-Bound Algorithm
  • Greedy Algorithms
  • NP-hard
  • Number Partitioning Problem

Fingerprint

Dive into the research topics of 'Separating the Yes- from the No-Instances in the Number Partitioning Problem'. Together they form a unique fingerprint.

Cite this