Booth Id:
MATH004
Category:
Mathematics
Year:
2023
Finalist Names:
Zhang, Meryl (School: R. C. Clark High School)
Abstract:
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 Won:
American Mathematical Society: One-Year Membership to American Mathematical Society to each winner (7 winning projects, up to 3 team members per project)
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
First Award of $5,000
American Mathematical Society: Third Award of $500
Association for Computing Machinery: Fourth Award of $500