The Easiest Hard Problem: A Heuristic Solution to the Two-Way Partitioning Problem Using Probabilistic Algorithms

Overview

The Two-Way Partitioning Problem is an NP-Complete problem that seeks to find a partition of a set of integers: given an input multiset S of n positive integers, separate the integers of S into two subsets such that sums of the subsets are as close to equal as possible. The accuracy of a partition is measured by the residue, or the difference between the sums of the two subsets. The Two-Way Partitioning Problem is one of Garey and Johnson’s six basic NP-hard problems that lie at the heart of the theory of NP-completeness (Mertens 2003). In this study, the starting solutions of probabilistic methods were experimented with, to potentially yield a more applicable and accurate algorithm. Namely, a pre-calculated solution done by the Karmarkar-Karp heuristic approach and a randomly generated starting solution were tested. Experimentation of the starting solutions was taken even further by testing different representations of starting solutions, namely sign and pre-partition representation. The starting solutions were then implemented on three probabilistic algorithms: repeated random, hill climbing, and simulated annealing to test performance rate. Results showed that algorithms with a randomly generated starting solution in pre-partition representation yielded lower residues by a factor of around 10^3 when compared to Karmarkar-Karp itself – a 99% increase in accuracy – leading to a more accurate, consistent, and applicable solution. The Two-Way Partitioning Problem has applications in a variety of fields, including security, social inequality, and military operations.

Awards (6)

• First Award of $5,000 $5,000
• American Mathematical Society: One-Year Membership to American Mathematical Society to each winner (7 winning projects, up to 3 team members per project)
• American Mathematical Society: Third Award of $500 $500
• Air Force Research Laboratory on behalf of the United States Air Force: Glass trophy and USAF medal for each recipient
• Air Force Research Laboratory on behalf of the United States Air Force: First Award of $750 in each Regeneron ISEF Category, FOR 2023 ONLY: EBED WILL HAVE TWO $750
• Association for Computing Machinery: Fourth Award of $500 $500

Competition history

• ISEF 2023 Mathematics · Entry MATH004 · Dallas, Texas, United States

Resources

• ISEF abstract page ↗

Related projects

Closest projects by meaning, across every fair and year in the corpus.