The complexity of facets (and some facets of complexity)
Christos H. Papadimitriou, Mihalis Yannakakis · 1982
Many important combinatorial optimization problems, including the traveling salesman problem (TSP), the clique problem and many others, call for the optimization of a linear functional over some discrete set of vectors.