Improved Approximation Algorithms for Label Cover Problems

Improved Approximation Algorithms for Label Cover Problems

0.00 Avg rating0 Votes
Article ID: iaor20116464
Volume: 61
Issue: 1
Start Page Number: 190
End Page Number: 206
Publication Date: Sep 2011
Journal: Algorithmica
Authors: , ,
Keywords: complexity, covering problems, random search
Abstract:

In this paper we consider both the maximization variant Max Rep and the minimization variant Min Rep of the famous Label Cover problem. So far the best approximation ratios known for these two problems were O ( n ) equ1 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/3log 2/3 n)‐approximation algorithm for Min Rep. In addition, we also exhibit a randomized reduction from Densest kSubgraph to Max Rep, showing that any approximation factor for Max Rep implies the same factor (up to a constant) for Densest kSubgraph.

Reviews

Required fields are marked *. Your email address will not be published.