Improved Approximation Algorithms for Label Cover Problems
In this paper we consider both the maximization variant MAX REP and the minimization variantMIN REP of the famous LABEL COVER problem. So far the best approximation ratios known for these two problems were O(root n) and indeed some authors suggested the possibility that this ratio is the best approximation factor for these two problems. We show, in fact, that there are a O(n(1/3))-approximation algorithm for MAX REP and a O(n(1/3)log(2/3) n)-approximation algorithm for MIN REP. In addition, we also exhibit a randomized reduction from DENSEST k-SUBGRAPH to MAX REP, showing that any approximation factor for MAX REP implies the same factor (up to a constant) for DENSEST k-SUBGRAPH.
approximation algorithm label cover max rep min rep densest k-subgraph hardness of approximation