Improved Approximation Algorithms for Label Cover Problems

DOI10.1007/978-3-642-04128-0_3MaRDI QIDQ3639232zbMATHOpenAlexFDO

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

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20) Approximation algorithms (68W25)

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

Cited in

(14)

• Approximation algorithms for the Label-Cover\(_{\text{MAX}}\) and Red-Blue Set Cover problems
• A New Point of NP-Hardness for 2-to-1 Label Cover
• A note on degree vs gap of Min-Rep label cover and improved inapproximability for connectivity problems
• A Linear-Time Parameterized Algorithm for Node Unique Label Cover
• On the maximum edge-pair embedding bipartite matching
• Approximation algorithms for label cover and the log-density threshold
• scientific article; zbMATH DE number 1617261 (Why is no real title available?)
• New results on the complexity of the Max- and Min-Rep problems
• Label Cover Instances with Large Girth and the Hardness of Approximating Basic k -Spanner
• scientific article; zbMATH DE number 7650076 (Why is no real title available?)
• On the hardness of approximating label-cover
• Improved approximation algorithms for label cover problems
• Finding paths with minimum shared edges
• Improved approximation algorithms for projection games (extended abstract)

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)