A Threshold of ln n for Approximating Set Cover-英文文献.pdf

A threshold of ln n for approximating set cover Uriel Feige  Department of Applied Math and Computer Science The Weizmann Institute Rehovot Israel feigewisdomweizmann acil April Abstract Given a collection F of subsets of S f ng set cover is the problem of select ing as few as p ossible subsets from F such that their union covers S and max k cover is the problem of selecting k subsets from F such that their union has maximum cardi nality Both these problems are NPhard We prove that o ln n is a threshold b elow which set cover cannot b e approximated eciently unless NP has slightly su p erp olynomial time algorithms This closes the gap up to low order terms b etween the ratio of approximation achievable by the greedy algorithm which is o ln n and previous results of Lund and Yannakakis that showed hardness of approximation within a ratio of log n ln n For max kcover we show an approximation 2 threshold of e up to low order terms under the assumption that P N P Intro duction Let S b e a set of n p oints and F fS S S g a collection of subsets of S Set s cover is the problem of selecting as few as p ossible subsets from F such that every p oint in S is contained in at least one of the selected subsets Max kcover is the problem of selecting k subsets from F such that their union contains as many p oints as p ossible Both these problems are NPhard A common approach of coping with NPhard problems is by approximation algorithms that run i