A Threshold of ln n for Approximating Set Cover II: The Inapproximability of Max k-CoverResearch Paper
Max -cover is the basic coverage problem of combinatorial optimization. The input is a collection of subsets of a finite ground set and a number ; the task is to choose subsets that together cover as many points as possible. It models facility and sensor placement, the selection of a small committee or feature set representing a population, and budgeted…