caa a22 4500 445805080 CHVBK 20180317145154.0 cr unu---uuuuu 170323e20110901xx s 000 0 eng 10.1007/s00453-010-9464-3 doi (NATIONALLICENCE)springer-10.1007/s00453-010-9464-3 Improved Approximation Algorithms for Label Cover Problems [Elektronische Daten] [Moses Charikar, MohammadTaghi Hajiaghayi, Howard Karloff] 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(\sqrt{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/3log 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. Springer Science+Business Media, LLC (outside the USA), 2011 Label Cover nationallicence Approximation algorithm nationallicence Hardness of approximation nationallicence Min Rep nationallicence Max Rep nationallicence Densest k -Subgraph nationallicence Charikar Moses Department of Computer Science, Princeton University, 08540, Princeton, NJ, USA aut Hajiaghayi MohammadTaghi University of Maryland at College Park, A.V. Williams Bldg., 20742, College Park, MD, USA aut Karloff Howard AT&T Labs—Research, 180 Park Ave., 07932, Florham Park, NJ, USA aut Algorithmica Springer-Verlag 61/1(2011-09-01), 190-206 0178-4617 61:1<190 2011 61 453 https://doi.org/10.1007/s00453-010-9464-3 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00453-010-9464-3 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Charikar Moses Department of Computer Science, Princeton University, 08540, Princeton, NJ, USA aut NATIONALLICENCE 700 1- Hajiaghayi MohammadTaghi University of Maryland at College Park, A.V. Williams Bldg., 20742, College Park, MD, USA aut NATIONALLICENCE 700 1- Karloff Howard AT&T Labs—Research, 180 Park Ave., 07932, Florham Park, NJ, USA aut NATIONALLICENCE 773 0- Algorithmica Springer-Verlag 61/1(2011-09-01), 190-206 0178-4617 61:1<190 2011 61 453 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer