Abstract
dc:descriptionIn this thesis, I survey 11 approximation algorithms for unweighted set cover problem. I have also implemented the three algorithms and created a software library that stores the code I have written. The algorithms I survey are: 1. Johnson's standard greedy; 2. f-frequency greedy; 3. Goldsmidt, Hochbaum and Yu's modified greedy; 4. Halldorsson's local optimization; 5. Dur and Furer semi local optimization; 6. Asaf Levin's improvement to Dur and Furer; 7. Simple rounding; 8. Randomized rounding; 9. LP duality; 10. Primal-dual schema; and 11. Network flow technique. Most of the algorithms surveyed are refinements of standard greedy algorithm.
Degree
thesis:*- Grantor dc:publisher
- University of North Texas
- Year dc:date
- 2009
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Dutta, Himanshu Shekhar
- Contributors dc:contributor
-
- Shahrokhi, Farhad
- Perez, Jose
- Huang, Yan
Subjects
dc:subject × 6Rights
dc:rights- Statement dc:rights
-
- Public
- Copyright
- Dutta, Himanshu Shekhar
- Copyright is held by the author, unless otherwise noted. All rights reserved.
- Language dc:language
- English
Identifiers
dc:identifier.*- Identifier
-
oclc: 608035515
untcat: b3828023
https://digital.library.unt.edu/ark:/67531/metadc12118/
ark: ark:/67531/metadc12118