Return to search

Survey of Approximation Algorithms for Set Cover Problem

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.

Identiferoai:union.ndltd.org:unt.edu/info:ark/67531/metadc12118
Date12 1900
CreatorsDutta, Himanshu Shekhar
ContributorsShahrokhi, Farhad, Perez, Jose, Huang, Yan
PublisherUniversity of North Texas
Source SetsUniversity of North Texas
LanguageEnglish
Detected LanguageEnglish
TypeThesis or Dissertation
FormatText
RightsPublic, Copyright, Dutta, Himanshu Shekhar, Copyright is held by the author, unless otherwise noted. All rights reserved.

Page generated in 0.0018 seconds