Improved approximation algorithms for projection games

DOI10.1007/S00453-015-0088-5MaRDI QIDQ513283zbMATH OpenOpenAlexFDO

Authors Pasin Manurangsi, Dana Moshkovitz

Publication date 3 March 2017

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1408.4048

zbMATH Keywords

approximation algorithmsLabel Coverprojection games

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Games involving graphs (91A43)

Abstract: 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. 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.

Recommendations

• Improved approximation algorithms for projection games (extended abstract)
• scientific article; zbMATH DE number 6474898
• The projection games conjecture and the NP-hardness of n-approximating Set-Cover
• Approximation algorithms for label cover and the log-density threshold
• On the hardness of approximating label-cover

Cites work

• A new PCP outer verifier with applications to homogeneous linear equations and max-bisection
• A Parallel Repetition Theorem
• A threshold of ln n for approximating set cover
• Analytical approach to parallel repetition
• Approximation algorithms for NP-complete problems on planar graphs
• Approximation algorithms for the Label-Cover\(_{\text{MAX}}\) and Red-Blue Set Cover problems
• Diameter and treewidth in minor-closed graph families
• Free Bits, PCPs, and Nonapproximability---Towards Tight Results
• Improved approximation algorithms for label cover problems
• Non-deterministic exponential time has two-prover interactive protocols
• On the power of unique 2-prover 1-round games
• Probabilistic checking of proofs
• Proof verification and the hardness of approximation problems
• Some optimal inapproximability results
• Some simplified NP-complete graph problems
• Subexponential algorithms for unique games and related problems
• The projection games conjecture and the NP-hardness of n-approximating Set-Cover
• Two-query PCP with subconstant error

Cited in

(7)

• Improved approximation algorithms for projection games (extended abstract)
• scientific article; zbMATH DE number 6474898 (Why is no real title available?)
• The projection games conjecture and the NP-hardness of n-approximating Set-Cover
• Playing Games with Approximation Algorithms
• Approximation algorithms for label cover and the log-density threshold
• Entropy samplers and strong generic lower bounds for space bounded learning
• On approximate reconfigurability of label cover

This page was built for publication: Improved approximation algorithms for projection games

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q513283)