Type
Text
Type
Dissertation
Advisor
Mitchell, Joseph S.B. | Arkin, Esther | Skiena, Steven | Gao, Jie.
Date
2015-08-01
Keywords
Operations research
Department
Department of Applied Mathematics and Statistics.
Language
en_US
Source
This work is sponsored by the Stony Brook University Graduate School in compliance with the requirements for completion of degree.
Identifier
http://hdl.handle.net/11401/76627
Publisher
The Graduate School, Stony Brook University: Stony Brook, NY.
Format
application/pdf
Abstract
Three problems in discrete optimization are considered and solved to varying degrees using novel algorithms. Worst case behavior experiments were run in all chapters. First, a seating arrangement problem is shown to be NP-hard. A simplified case is solved using a greedy algorithm and we use a two phase approach to find a 2-factor approximation for a slightly more complex version of the problem. Next, we bound the performance of a recently published approach to DNA copy number analysis. We then devise a dynamic programming PTAS and an integer programming formulation which outperformed the published approach. Finally, we introduce a dynamic load balancing problem. For this NP-hard problem we devise a lower bound, a 2.7-factor heuristic and an experimentally promising heuristic. We experimentally compared the solution quality of our algorithms to some suggested heuristics. | 74 pages
Recommended Citation
Zuber, James Robert, "Probing the Knowable Unknown" (2015). Stony Brook Theses and Dissertations Collection, 2006-2020 (closed to submissions). 2517.
https://commons.library.stonybrook.edu/stony-brook-theses-and-dissertations-collection/2517