Improved Approximation Algorithms for Projection Games

详细信息    查看全文

• 作者：Pasin Manurangsi ; Dana Moshkovitz
• 关键词：Label Cover ; Projection games ; Approximation algorithms
• 刊名：Algorithmica
• 出版年：2017
• 出版时间：February 2017
• 年：2017
• 卷：77
• 期：2
• 页码：555-594
• 全文大小：
• 刊物类别：Computer Science
• 刊物主题：Algorithm Analysis and Problem Complexity; Theory of Computation; Mathematics of Computing; Algorithms; Computer Systems Organization and Communication Networks; Data Structures, Cryptology and Inform
• 出版者：Springer US
• ISSN：1432-0541
• 卷排序：77

文摘

The projection games (aka Label Cover) problem is of great importance to the field of approximation algorithms, since most of the NP-hardness of approximation results we know today are reductions from Label Cover. In this paper we design several approximation algorithms for projection games: (1) A polynomial-time approximation algorithm that improves on the previous best approximation by Charikar et al. (Algorithmica 61(1):190–206, 2011). (2) A sub-exponential time algorithm with much tighter approximation for the case of smooth projection games. (3) A polynomial-time approximation scheme (PTAS) for projection games on planar graphs and a tight running time lower bound for such approximation schemes. The conference version of this paper had only the PTAS but not the running time lower bound.