A short tour of combinatorial optimization and computational complexity
Maurício G. C. Resende, Celso Carneiro Ribeiro · 2016
This chapter introduces combinatorial optimization problems and their computational complexity. We first formulate some fundamental problems already introduced in the previous chapter and then consider basic concepts of the theory of computational complexity, with special emphasis on decision problems, polynomial-time algorithms, and NP -complete problems. The chapter concludes with a discussion of solution approaches for NP -hard problems, introducing constructive heuristics, local search or improvement procedures and, finally, metaheuristics. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.