The Easiest Hard Problem: Now Even Easier

Ruben Horn, Sarah L. Thomson*, Daan Van Den Berg, Pieter Adriaans

*Corresponding author for this work

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

Abstract

We present an exponential decay function that characterizes the number of solutions to instances of the Number Partitioning Problem (NPP) with uniform distribution of bits across the integers. This function is fitted on the number of optimal solutions of random instances with lengths between 10 and 20 integers and may be used as a heuristic either directly by new algorithms for the NPP or as a benchmark to evaluate how well different Evolutionary Algorithms (EAs) cover the search space. Despite the long history of the NPP, it seems such a characterization does not yet exist.

Original languageEnglish
Title of host publicationGECCO '24 Companion
Subtitle of host publicationProceedings of the Genetic and Evolutionary Computation Conference Companion
PublisherAssociation for Computing Machinery, Inc
Pages97-98
Number of pages2
ISBN (Electronic)9798400704956
DOIs
Publication statusPublished - 2024
Event2024 Genetic and Evolutionary Computation Conference Companion, GECCO 2024 Companion - Melbourne, Australia
Duration: 14 Jul 202418 Jul 2024

Conference

Conference2024 Genetic and Evolutionary Computation Conference Companion, GECCO 2024 Companion
Country/TerritoryAustralia
CityMelbourne
Period14/07/2418/07/24

Bibliographical note

Publisher Copyright:
© 2024 Copyright held by the owner/author(s).

Keywords

  • combinatorial optimization
  • number partitioning problem
  • the easiest hard problem

Fingerprint

Dive into the research topics of 'The Easiest Hard Problem: Now Even Easier'. Together they form a unique fingerprint.

Cite this