Improved approximation algorithms for label cover problems
From MaRDI portal
Publication:634686
DOI10.1007/S00453-010-9464-3zbMATH Open1218.68197OpenAlexW2108967854MaRDI QIDQ634686FDOQ634686
Authors: Moses Charikar, Mohammad T. Hajiaghayi, Howard 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
Recommendations
- Improved Approximation Algorithms for Label Cover Problems
- Approximation algorithms for label cover and the log-density threshold
- New results on the complexity of the Max- and Min-Rep problems
- On the hardness of approximating label-cover
- Approximation algorithms for the Label-Cover\(_{\text{MAX}}\) and Red-Blue Set Cover problems
approximation algorithmhardness of approximation\textsc{Densest \(k\)-Subgraph}\textsc{Label Cover}\textsc{Max Rep}\textsc{Min Rep}
Cites Work
- Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
- Detecting high log-densities, an \(O(n^{1/4})\) approximation for densest \(k\)-subgraph
- On network design problems: fixed cost flows and the covering steiner problem
- Title not available (Why is that?)
- Stochastic Steiner Tree with Non-uniform Inflation
- The hardness of approximate optima in lattices, codes, and systems of linear equations
- The hardness of approximating spanner problems
- Power optimization for connectivity problems
- Hardness of Approximation for Vertex-Connectivity Network Design Problems
- Approximation algorithms for the Label-Cover\(_{\text{MAX}}\) and Red-Blue Set Cover problems
- Design networks with bounded pairwise distance
- Approximating the minimal sensor selection for supervisory control
- Title not available (Why is that?)
- On the hardness of approximating spanners
- Transitive-closure spanners
- Disjoint-path facility location: theory and practice
- FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
- Approximation Algorithms and Hardness for Domination with Propagation
Cited In (20)
- On the approximability of the minimum rainbow subgraph problem and other related problems
- A note on degree vs gap of Min-Rep label cover and improved inapproximability for connectivity problems
- Approximation algorithms for label cover and the log-density threshold
- Sherali-Adams integrality gaps matching the log-density threshold
- From gap-exponential time hypothesis to fixed parameter tractable inapproximability: clique, dominating set, and more
- ETH-hardness of approximating 2-CSPs and directed Steiner network
- Lasserre integrality gaps for graph spanners and related problems
- A Linear-Time Parameterized Algorithm for Node Unique Label Cover
- Title not available (Why is that?)
- Approximation algorithms for the Label-Cover\(_{\text{MAX}}\) and Red-Blue Set Cover problems
- On the hardness of approximating label-cover
- Improved Approximation Algorithms for Label Cover Problems
- Sum-of-squares lower bounds for densest \(k\)-subgraph
- A New Point of NP-Hardness for 2-to-1 Label Cover
- Near-optimal NP-hardness of approximating \textsc{Max} \(k\)-\(\mathrm{CSP}_R\)
- New results on the complexity of the Max- and Min-Rep problems
- Improved approximation algorithms for projection games
- Title not available (Why is that?)
- Label Cover Instances with Large Girth and the Hardness of Approximating Basic k -Spanner
- Minimum label \(s\)-\(t\) cut has large integrality gaps
This page was built for publication: Improved approximation algorithms for label cover problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q634686)
