| dc.identifier.uri | http://hdl.handle.net/11401/76627 | |
| dc.description.sponsorship | This work is sponsored by the Stony Brook University Graduate School in compliance with the requirements for completion of degree. | en_US |
| dc.format | Monograph | |
| dc.format.medium | Electronic Resource | en_US |
| dc.language.iso | en_US | |
| dc.publisher | The Graduate School, Stony Brook University: Stony Brook, NY. | |
| dc.type | Dissertation | |
| dcterms.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. | |
| dcterms.available | 2017-09-20T16:50:49Z | |
| dcterms.contributor | Mitchell, Joseph S.B. | en_US |
| dcterms.contributor | Arkin, Esther | en_US |
| dcterms.contributor | Skiena, Steven | en_US |
| dcterms.contributor | Gao, Jie. | en_US |
| dcterms.creator | Zuber, James Robert | |
| dcterms.dateAccepted | 2017-09-20T16:50:49Z | |
| dcterms.dateSubmitted | 2017-09-20T16:50:49Z | |
| dcterms.description | Department of Applied Mathematics and Statistics. | en_US |
| dcterms.extent | 74 pg. | en_US |
| dcterms.format | Monograph | |
| dcterms.format | Application/PDF | en_US |
| dcterms.identifier | http://hdl.handle.net/11401/76627 | |
| dcterms.issued | 2015-08-01 | |
| dcterms.language | en_US | |
| dcterms.provenance | Made available in DSpace on 2017-09-20T16:50:49Z (GMT). No. of bitstreams: 1
Zuber_grad.sunysb_0771E_12019.pdf: 429027 bytes, checksum: 85632430196c8511b0a601802a09179b (MD5)
Previous issue date: 2014 | en |
| dcterms.publisher | The Graduate School, Stony Brook University: Stony Brook, NY. | |
| dcterms.subject | Operations research | |
| dcterms.title | Probing the Knowable Unknown | |
| dcterms.type | Dissertation | |
