Change search
ReferencesLink to record
Permanent link

Direct link
A New Point of NP-Hardness for 2-to-1 Label Cover
University of Toronto.ORCID iD: 0000-0001-8217-0158
Carnegie Mellon University.
Carnegie Mellon University.
2012 (English)In: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2012, 1-12 p.Conference paper (Refereed)
Abstract [en]

We show that given a satisfiable instance of the 2-to-1 Label Cover problem, it is NP-hard to find a (23/24 + ε)-satisfying assignment

Place, publisher, year, edition, pages
2012. 1-12 p.
National Category
Computer Science
URN: urn:nbn:se:kth:diva-112870DOI: 10.1007/978-3-642-32512-0_1ScopusID: 2-s2.0-84865300564OAI: diva2:587541
15th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2012 and the 16th International Workshop on Randomization and Computation, RANDOM 2012; Cambridge, MA; United States

QC 20130523

Available from: 2013-01-14 Created: 2013-01-14 Last updated: 2013-05-23Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Austrin, Per
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 7 hits
ReferencesLink to record
Permanent link

Direct link