Improved approximation algorithms for label cover problems

DOI10.1007/s00453-010-9464-3zbMath1218.68197OpenAlexW2108967854MaRDI QIDQ634686

Moses Charikar, Mohammad Taghi Hajiaghayi, Howard J. Karloff

Publication date: 16 August 2011

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-010-9464-3

zbMATH Keywords

approximation algorithmhardness of approximation\textsc{Densest \(k\)-Subgraph}\textsc{Label Cover}\textsc{Max Rep}\textsc{Min Rep}

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Approximation algorithms (68W25)

Related Items (8)

On the approximability of the minimum rainbow subgraph problem and other related problems ⋮ From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More ⋮ Unnamed Item ⋮ Minimum label \(s\)-\(t\) cut has large integrality gaps ⋮ ETH-Hardness of Approximating 2-CSPs and Directed Steiner Network ⋮ Improved approximation algorithms for projection games ⋮ Unnamed Item ⋮ Lasserre integrality gaps for graph spanners and related problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximating the minimal sensor selection for supervisory control
• Power optimization for connectivity problems
• Approximation algorithms for the Label-Cover\(_{\text{MAX}}\) and Red-Blue Set Cover problems
• The hardness of approximate optima in lattices, codes, and systems of linear equations
• The hardness of approximating spanner problems
• Design networks with bounded pairwise distance
• Detecting high log-densities
• On network design problems: fixed cost flows and the covering steiner problem
• Stochastic Steiner Tree with Non-uniform Inflation
• Hardness of Approximation for Vertex-Connectivity Network Design Problems
• Disjoint-Path Facility Location: Theory and Practice
• Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
• FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
• Approximation Algorithms and Hardness for Domination with Propagation
• On the hardness of approximating spanners

This page was built for publication: Improved approximation algorithms for label cover problems