Back to search

University of North Texas

Survey of Approximation Algorithms for Set Cover Problem

Abstract

dc:description

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.

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 × 6

Rights

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

Chain of custody

source
Harvested from
University of North Texas
Base URL
digital.library.unt.edu/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Dutta, Himanshu Shekhar. Survey of Approximation Algorithms for Set Cover Problem. University of North Texas, 2009. https://doi.org/10.12794/metadc12118