Approximability of hard combinatorial optimization problems: An introduction

Most Combinatorial Optimization (CO for short) problems are hard to solve exactly, in the sense that all known approaches have a worst-case computing time growing exponentially with the dimension of the instance being considered. Even if on average these methods have proved to work much more satisfactorily than their worst-case performance would suggest, the need for efficient (i.e., polynomial) approximate algorithms in order to cope with instances of large size was already recognized in the early seventies, shortly after the pioneering works of Cook and Karp marking the birth of NP-completeness. As is well-known, the theory of NP-completeness deals with language recognition problems, whereas the theory of approximability is concerned with the corresponding optimization problems. This fact alone suggests that the study of approximability properties for optimization problems whose recognition version is NP-complete implies more subtle difficulties than that of NP-completeness. In this paper we introduce the reader into the fascinating field of approximability of hard CO problems, assuming on his/her side only some familiarity with the main concepts of NP-completeness as presented in many Combinatorial Optimization textbooks. We follow almost a historic path, reviewing early results in section 3, after having presented some basic definitions in section 2. More recent developments in the theoretical characterization of approximation classes are described in sections 4 and 5. Section 6 is devoted to some applications and remarks. An in-depth description of the many sophisticated algorithms for solving approximately NP-hard CO problems is beyond the scope of this work.