Approximation Algorithms for Combinatorial Problems IV: Greedy Set Cover C1 Has Worst-Case Ratio H(k) on SC(k)Research Paper
Set covering asks for the fewest members of a family of sets whose union is everything the family covers. It models crew scheduling, facility siting, test-suite reduction, logic minimization and fault testing; Johnson names the last two as its practical applications. Karp showed in 1972 that the decision version is NP-complete (Karp 1972), so in practice…