In 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.
| Identifer | oai:union.ndltd.org:unt.edu/info:ark/67531/metadc12118 |
| Date | 12 1900 |
| Creators | Dutta, Himanshu Shekhar |
| Contributors | Shahrokhi, Farhad, Perez, Jose, Huang, Yan |
| Publisher | University of North Texas |
| Source Sets | University of North Texas |
| Language | English |
| Detected Language | English |
| Type | Thesis or Dissertation |
| Format | Text |
| Rights | Public, Copyright, Dutta, Himanshu Shekhar, Copyright is held by the author, unless otherwise noted. All rights reserved. |
Page generated in 0.0022 seconds