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.0111 seconds