A brief history of NP-completeness, 1954--2012

zbMath1260.68007MaRDI QIDQ1946035

David S. Johnson

Publication date: 17 April 2013

Published in: Documenta Mathematica (Search for Journal in Brave)

Full work available at URL: http://www.emis.de/journals/DMJDMV/vol-ismp/50_johnson-david.html

zbMATH Keywords

NP-completenesspolynomial timeapproximation algorithmsbin packingunique games conjecture

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Semidefinite programming (90C22) Linear programming (90C05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) History of computer science (68-03)

Related Items (2)

Tensors in computations ⋮ A historical note on the complexity of scheduling problems

Uses Software

• Concorde

This page was built for publication: A brief history of NP-completeness, 1954--2012