Improved approximation algorithms for label cover problems
From MaRDI portal
Publication:634686
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
approximation algorithmhardness of approximation\textsc{Densest \(k\)-Subgraph}\textsc{Label Cover}\textsc{Max Rep}\textsc{Min Rep}
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
