The NP-Completeness Column: An Ongoing Guide

By David S. Johnson. 1982

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Efficient Representations for Lifelong Learning and Autoencoding (2014, background): “That is, given a collection of conjunctions, it is NP-hard to determine whether there exist k monomials such that each can be written as a product of subsets of those monomials (it is called the “set-basis problem” [12]).”
Domain and Function: A Dual-Space Model of Semantic Relations and Compositions (2012, background): “Also, in general, quadratic growth is often acceptable in practical applications (Garey & Johnson, 1979).”
The limits of automatic summarisation according to ROUGE (2017, background): “in which the degree of all vertices is equal to 3) (Garey and Johnson, 1979).”
Substructure similarity search in graph databases (2005, unknown): “Unfortunately, it is NP-complete [6].”
Topology control and routing in ad hoc networks: a survey (2002, background): “The problem of finding a dominating set of minimum size, however, is a classic NP-complete optimization problem [ 18 ] and it is known that unless NP has n °(l°g t°g~)-time deterministic algorithms, the best approximation ratio achievable in polynomial time is O(log n) [15].”
Combinatorial problems raised from 2-semilattices (2006, background): “Note that CSP({ =D}) precisely corresponds to the GRAPH |D|-COLORABILITY problem [19].”
Sparse Approximate Solutions to Linear Systems (1995, background): “Also, the "minimum set cover" problem can be viewed as computing a sparse solution to Ax >_ b, where all the entries are binary and the inequality is entry-wise; see Garey and Johnson (1979), Johnson (1974).”
Max-linear Systems: Theory and Algorithms (2010, background): “For instance the task of nding a solution to A x = b with the minimum number of components equal to x is polynomially equivalent to the minimum cardinality set cover problem and is therefore NP -complete [83].”
Kernelized Sorting (2008, background): “Note that the optimization problem (5) is in the form of Koopmans-Beckmann equation [13] and is in general NP hard as it is an instance of a quadratic assignment problem [14].”
Object replication strategies in content distribution networks (2002, unknown): “This problem is identical to the well-known NPcomplete knapsack problem [6].”
A New Placement Heuristic for the Orthogonal Stock-Cutting Problem (2004, background): “The two-dimensional variant of the stock-cutting problem is NP hard due to the combinatorial explosion encountered as the problem size increases ( Garey and Johnson 1979 ).”
Static pickup and delivery problems: a classification scheme and survey (2007, background): “As noted by Anily and Hassin (1992), the SP is NP-hard (Garey and Johnson 1979), even for a unit capacity vehicle.”
Workforce planning incorporating skills: State of the art (2015, methodology): “[113] P. H. Vance, C. Barnhart, E. L. Johnson and G. L. Nemhauser.”
GPLAG: detection of software plagiarism by program dependence graph analysis (2006, background): “Although subgraph isomorphism is NP-complete in general [5], research in the past three decades has shown that some algorithms are reasonably fast on average and become computationally intractable only in a few cases [6] [7].”
A Survey of the Quadratic Assignment Problem, with Applications (2003, background): “Creating lower bounds for a given QAP(C;D) based on the eigenvalues of C and D has been researched extensively [ 17 , 22, 23, 37].”