On the hardness of approximating label-cover

DOI10.1016/j.ipl.2003.11.007zbMath1178.68676OpenAlexW2070989606MaRDI QIDQ1029090

Shmuel Safra, Irit Dinur

Publication date: 9 July 2009

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2003.11.007

zbMATH Keywords

computational complexityhardness of approximationPCPlabel-cover

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (14)

Secluded connectivity problems ⋮ Towards NP-P via proof complexity and search ⋮ Approximation and hardness results for label cut and related problems ⋮ Sparse weighted voting classifier selection and its linear programming relaxations ⋮ Approximation algorithms for the Label-Cover\(_{\text{MAX}}\) and Red-Blue Set Cover problems ⋮ Cost-optimal Planning, Delete Relaxation, Approximability, and Heuristics ⋮ Target set selection for conservative populations ⋮ Hardness results for approximate pure Horn CNF formulae minimization ⋮ On the maximum edge-pair embedding bipartite matching ⋮ On the positive-negative partial set cover problem ⋮ Frugal Routing on Wireless Ad-Hoc Networks ⋮ A note on the subadditive network design problem ⋮ On the hardness of approximating the min-hack problem ⋮ Precedence-Constrained Min Sum Set Cover

Cites Work

• Unnamed Item
• Unnamed Item
• Approximation algorithms for combinatorial problems
• On the ratio of optimal integral and fractional covers
• PCP characterizations of NP
• On the hardness of approximating minimization problems
• A Parallel Repetition Theorem
• Intractability of assembly sequencing: Unit disks in the plane

This page was built for publication: On the hardness of approximating label-cover