Improved Approximation Algorithms for Projection Games

被引：0
|
作者：
Manurangsi, Pasin [1 ]
Moshkovitz, Dana [1 ]
机构：
[1] MIT, Cambridge, MA 02139 USA
来源：
ALGORITHMS - ESA 2013 | 2013年 / 8125卷
关键词：
Label-Cover; projection games; HARDNESS;
D O I：
暂无
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
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, Hajiaghayi and Karloff [7]. 2. A sub-exponential time algorithm with much tighter approximation for the case of smooth projection games. 3. A PTAS for planar graphs.
引用
收藏
页码：683 / 694
页数：12
相关论文
共 50 条
  • [1] Improved Approximation Algorithms for Projection Games
    Manurangsi, Pasin
    Moshkovitz, Dana
    ALGORITHMICA, 2017, 77 (02) : 555 - 594
  • [2] Improved Approximation Algorithms for Projection Games
    Pasin Manurangsi
    Dana Moshkovitz
    Algorithmica, 2017, 77 : 555 - 594
  • [3] Playing Games with Approximation Algorithms
    Kakade, Sham M.
    Kalai, Adam Tauman
    Ligett, Katrina
    STOC 07: PROCEEDINGS OF THE 39TH ANNUAL ACM SYMPOSIUM ON THEORY OF COMPUTING, 2007, : 546 - 555
  • [4] Approximation Algorithms for Unique Games
    Department of Electrical Engineering and Computer Science, University of California, Berkeley
    CA
    94720-1776, United States
    Theory Comput., 2008, (111-128):
  • [5] Approximation algorithms and network games
    Tardos, É
    ALGORITHMS - ESA 2003, PROCEEDINGS, 2003, 2832 : 6 - 6
  • [6] Approximation algorithms for unique games
    Trevisan, L
    46TH ANNUAL IEEE SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS, 2005, : 197 - 205
  • [7] PLAYING GAMES WITH APPROXIMATION ALGORITHMS
    Kakade, Sham M.
    Kalai, Adam Tauman
    Ligett, Katrina
    SIAM JOURNAL ON COMPUTING, 2009, 39 (03) : 1088 - 1106
  • [8] Iterative projection approximation algorithms for PCA
    Choi, Seungjin
    Ahn, Jong-Hoon
    Cichocki, Andrzej
    2006 IEEE International Conference on Acoustics, Speech and Signal Processing, Vols 1-13, 2006, : 5703 - 5706
  • [9] IMPROVED ALGORITHMS FOR UNSUPERVISED DISCRIMINANT PROJECTION
    Park, Cheong Hee
    INTERNATIONAL JOURNAL OF PATTERN RECOGNITION AND ARTIFICIAL INTELLIGENCE, 2010, 24 (02) : 193 - 206
  • [10] Retrograde approximation algorithms for jeopardy stochastic games
    Fang, Haw-ren
    Glenn, James
    Kruskal, Clyde P.
    ICGA JOURNAL, 2008, 31 (02) : 77 - 96
12345