A polynomial time heuristic algorithm for certain instances of 3-partition

Loading...
Thumbnail Image
Authors
Smith, Ronald Douglas
Advisor
Zage, Dolores M.
Issue Date
2014-05-03
Keyword
Degree
Thesis (M.S.)
Department
Department of Computer Science
Other Identifiers
Abstract

There are problems in computational complexity so difficult that the only known ways to solve them are impractical. A problem that has a few hundred inputs may take more time to solve with a super computer than the time that has passed since the beginning of the universe. One of these problems is the strongly NP-Complete 3-Partition. The goal of this thesis is to examine a fast heuristic algorithm that can solve 3-Partition quickly in certain cases but in the worst case may not find a solution even though one exists.

Collections