A polynomial time heuristic algorithm for certain instances of 3-partition
Loading...
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
CardCat URL
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.