A Threshold of ln n for Approximating Set Cover I: The ln n Inapproximability of Set CoverResearch Paper
Set cover is the problem of covering a finite ground set with as few members of a given family of subsets as possible. It models facility location, crew scheduling, test-suite minimization and many other selection problems in operations research, and it is one of the canonical NP-hard problems. The greedy algorithm, which repeatedly picks the subset…