Restricted parameter range promise set cover problems are easy

摘要

The restricted parameter range set cover problem is a weak form of the NP-hard set cover problem with the restricted range of parameters. We give a polynomial time algorithm for this problem by lattices.