Improved Approximation Algorithms for Label Cover Problems
From MaRDI portal
Publication:3639232
DOI10.1007/978-3-642-04128-0_3zbMATH Open1256.68161OpenAlexW4248550452MaRDI QIDQ3639232FDOQ3639232
Authors: Moses Charikar, Mohammad T. Hajiaghayi, Howard Karloff 
Publication date: 29 October 2009
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-04128-0_3
Recommendations
- Improved approximation algorithms for label cover problems
- On the hardness of approximating label-cover
- Approximation algorithms for label cover and the log-density threshold
- New results on the complexity of the Max- and Min-Rep problems
- Approximation algorithms for the Label-Cover\(_{\text{MAX}}\) and Red-Blue Set Cover problems
Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20) Approximation algorithms (68W25)
Cited In (14)
- On the maximum edge-pair embedding bipartite matching
- 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
- 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 projection games (extended abstract)
- Finding paths with minimum shared edges
- A New Point of NP-Hardness for 2-to-1 Label Cover
- New results on the complexity of the Max- and Min-Rep problems
- Title not available (Why is that?)
- Improved approximation algorithms for label cover problems
- Label Cover Instances with Large Girth and the Hardness of Approximating Basic k -Spanner
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 Q3639232)
