"Compendium of NP Optimization Problems 001.ps.gz" - читать интересную книгу автораThis a preliminary version of the catalog of NP optimization problems Please send any comment or suggestion to one of the two authors A compendium of NP optimization problems P. Crescenzi1 and V. Kann2 1 Dipartimento di Scienze dell'Informazione, Universit`a degli Studi di Roma "La Sapienza", Via Salaria 113, 00198 Rome, Italy. E-mail: [email protected] 2 Department of Numerical Analysis and Computing Science, Royal Institute of Technology, S-100 44 Stockholm, Sweden. E-mail: [email protected] September 27, 1994 Summary. Due to the fact that no NP-complete problem can be solved in polynomial time (unless P=NP), many approximability results (both positive and negative) of NP-hard optimization problems have appeared in the technical literature. In this compendium, we collect together a large number of these results. In the following we refer to standard complexity classes (see [Johnson, 1990]). We recall that a function t(n) is `quasi-polynomial' if a constant c exists such that t(n) ^ nlog c n and we denote by QP, QNP, and QR the analogues of the usual complexity classes in the quasi-polynomial time domain. 1. NPO Problems: Definitions and Preliminaries The basic ingredients of an optimization problem are the set of instances or input objects, the set of feasible solutions or output objects associated to any instance, and the measure defined for any feasible solution. On the analogy of the theory of NP-completeness, we are interested in studying a class of optimization problems whose feasible solutions are short and easy-torecognize. To this aim, suitable constraints have to be introduced. We thus give the following definition. 1. I is the set of the instances of A and it is recognizable in polynomial time. 2. Given an instance x of I, sol(x) denotes the set of feasible solutions of x. These solutions are short, that is, a polynomial p exists such that, for any y 2 sol(x), jyj ^ p(jxj). Moreover, it is decidable in polynomial time whether, for any x and for any y such that jyj ^ p(jxj), y 2 sol(x). 3. Given an instance x and a feasible solution y of x, m(x; y) denotes the positive integer measure of y. The function m is computable in polynomial time and is also called the objective function. 4. goal 2 fmax; ming. A compendium of NP optimization problems 2 The class NPO is the set of all NP optimization problems. The goal of an NPO problem with respect to an instance x is to find an optimum solution, that is, a feasible solution y such that m(x; y) = goalfm(x; y0) : y0 2 sol(x)g: In the following sol\Lambda will denote the multi-valued function mapping an instance x to the set of optimum solutions, while opt will denote the function mapping an instance x to the measure of an optimum solution. An NPO problem is said to be polynomially bounded if a polynomial q exists such that, for any instance x and for any solution y of x, m(x; y) ^ q(jxj). The class NPO PB is the set of polynomially bounded NPO problems. 2. Approximate Algorithms and Approximation Classes It is well-known that if an NPO problem can be solved in polynomial time, then its corresponding decision problem can also be solved in polynomial time. As a consequence, if P 6= NP, then any NPO problem whose corresponding decision problem is NP-complete is not solvable in polynomial time. In these cases we sacrifice optimality and start looking for approximate solutions computable in polynomial time. Definition 2. Let A be an NPO problem. Given an instance x and a feasible solution y of x, we define the performance ratio of y with respect to x as |
|
|