Nội dung

Yugoslav Journal of Operations Research Vol 19 (2009), Number 1, 3-40 DOI: 10.2298/YUJOR0901003P AN OVERVIEW ON POLYNOMIAL APPROXIMATION OF NP-HARD PROBLEMS Vangelis Th. PASCHOS LAMSADE, CNRS UMR 7024 and University Paris-Dauphine Place du Maréchal de Lattre de Tassigny, France paschos@lamsade.dauphine.fr Received: December 2007 / Accepted: May 2009 Abstract: The fact that polynomial time algorithm is very unlikely to be devised for an optimal solving of the NP-hard problems strongly motivates both the researchers and the practitioners to try to solve such problems heuristically, by making a trade-off between computational time and solution’s quality. In other words, heuristic computation consists of trying to find not the best solution but one solution which is “close to” the optimal one in reasonable time. Among the classes of heuristic methods for NP-hard problems, the polynomial approximation algorithms aim at solving a given NP-hard problem in polynomial time by computing feasible solutions that are, under some predefined criterion, as near to the optimal ones as possible. The polynomial approximation theory deals with the study of such algorithms. This survey first presents and analyzes time approximation algorithms for some classical examples of NP-hard problems. Secondly, it shows how classical notions and tools of complexity theory, such as polynomial reductions, can be matched with polynomial approximation in order to devise structural results for NP-hard optimization problems. Finally, it presents a quick description of what is commonly called inapproximability results. Such results provide limits on the approximability of the problems tackled. Keywords: Computational complexity, approximation algorithms. 1. WHAT IS POLYNOMIAL APPROXIMATION AND WHY WE DO IT? It is widely believed that no polynomial algorithm can be devised for an optimal solving of the NP-hard problems. So, several approaches, more or less satisfactory, can be followed when one tries to solve them. Roughly speaking, these approaches belong to one of the following two families. 4 V. Th. Paschos / An Overview on Polynomial Approximation of NP-hard Problems Exact (optimal) algorithms, that compute optimal solutions for the problems but run in exponential time; such algorithms are based upon either search tree-based methods (branch-and-bound, branch-and-cut, branch-and-price, etc.), or upon dynamic programming etc. Heuristic methods, that run faster than the exact algorithms and compute suboptimal solutions (that are, sometimes, unfeasible); the most notorious among these methods being: • the polyhedral methods, • the metaheuristics (simulated annealing, genetic algorithms, tabou, etc.), • the polynomial approximation algorithms with (a priori) performance guarantees. The goal of this overview is to make a general presentation of the last category of heuristic methods, that is, the polynomial approximation algorithms. What is polynomial approximation? Roughly speaking, this is the art to achieve feasible solutions with the objective value as close as possible (in some predefined sense) to the optimal value in polynomial time. How can we do it? Hopefully, the reader will see it in what follows. Why do we use polynomial approximation rather than other heuristic methods? There are several reasons for that. The main reasons are, in our opinion, both “operational” and “structural”. A central operational reason is that there are problems that describe natural situations and either require feasible solutions to be obtained quickly (i.e., in polynomial time) and this fact must be guaranteed a priori, or where optimum is misdefined or senseless. Also, it is sometimes necessary for a decision maker to have an a priori estimation of the performance of the algorithms used in the context of handling these problems. On the other hand, the main structural reason is that polynomial approximation is a natural extension of the complexity theory into the combinatorial optimization and it largely contributes to the enrichment of both these domains. The aim of the study of polynomial approximation of combinatorial optimization problems is to characterize the ability of a specific problem to be “wellsolved” in polynomial time. This is done by determining both the upper and the lower bounds of approximability, i.e., by exhibiting specific approximation algorithms that have achieved a given level of approximation on one side, and, on the other side, showing that no algorithm can possibly provide a better approximation level, until something strange and unexpected happens, i.e., until a very highly improbable complexity hypothesis (e.g., P = NP) holds. The existence of polynomial approximation as a scientific area was started by a seminal paper by [46]. Since then, this research programme is one of the most active research programmes in operational research, combinatorial optimization and theoretical computer science. 2. PRELIMINARIES The object of polynomial approximation is the class of the so-called NPO problems. Informally, this is the class of optimization problems the “decision”counterparts of which are in NP. Let us recall that, for a maximization problem (the case V. Th. Paschos / An Overview on Polynomial Approximation of NP-hard Problems 5 of a minimization problem is completely analogous), its decision version can be expressed as follows: “Is there a solution with value greater than, or equal to K ?”, where K is a constant that, for the decision version, is a part of the instance. Solving a decision problem Π becomes to answer the question defining Π by yes or no correctly. For example, for the decision version of MAX INDEPENDENT SET 1 : “given a graph G and a constant K , is there an independent set of G of the size at least K ?”, to solve it becomes to correctly answer the question if G has an independent set of size at least K or not. Formally, an NPO problem Π is a four-tuple (I, Sol, m, goal) such that: • I is the set of instances (recognizable in polynomial time); • for I ∈ I, Sol( I ) is the set of feasible solutions of I ; feasibility of any solution can be decided on in polynomial time; • for any I ∈ I, at least one feasible solution can be computed in polynomial time; • the objective value m( I , S ) of any solution S , is computable in polynomial time; • goal ∈ {min, max} . We shall now briefly present some of the basic notions of the polynomial approximation theory. More details can be found in [5, 44, 66, 72]. Having given an instance I of a combinatorial maximization (resp., minimization) problem Π = (I, Sol, m, goal), we denote by ω ( I ) , mA ( I , S ) and opt ( I ) the value of the worst solution of I (in the sense of objective function), the value of a solution S (computed by some polynomial time approximation algorithm A supposed to feasibly solve the problem Π ), and the optimal value 2 for I , respectively. The worst solution of I is the optimal solution for I with respect to the NPO problem Π′ = (I, Sol, m, goal′) where: T There exist mainly two paradigms dealing with polynomial approximation. Standard approximation. The quality of an approximation algorithm A is expressed by the ratio: Note that the approximation ratio for minimization problems is in [1, ∞ ) , while for the maximization ones this ratio is in (0,1] . Differential approximation. The quality of an approximation algorithm A is expressed by the ratio: 1 We properly define this problem in Section 4.1. 2 The value of an optimal solution. 6 V. Th. Paschos / An Overview on Polynomial Approximation of NP-hard Problems The value of the differential ratio is always in [0,1] , independently on the optimization goal of the problem. For both paradigms, the closer the ratios are to 1, the better the performance of the approximation algorithm A. Let us also note that, as we will see, the results obtained by adopting one or the other of the two paradigms are very often different even for the same problem. The rest of the paper has been organized as follows. In Section 3 the main approximability classes have been defined. In Section 4 we have analyzed the polynomial approximation algorithms for several well-known hard optimization problems. In Section 5, we have shown how the main tool of the complexity theory, polynomial reductions, can be adapted to the framework of polynomial approximation, in order to produce structural results. In Section 6 we have said a few words about the limits of approximability, i.e., for inapproximability of NP-hard problems. Providing inapproximability results that state that a specific problem is not approximable within better than some approximation level is crucial (although somewhat far from the classical operational researchers concerns; for this reason this part of the paper will be short) for characterizing the approximability of NP-hard problems and for the understanding of their structure. Finally, in Section 7 we have presented a quick overview on the completeness result in the approximation classes. To be brief, only the problems discussed in detail in this paper will be defined. For the other ones, the interested reader can referred to [35]. Also, for the notions and definitions of the graph theory, one can refered to [16]. 3. APPROXIMATION CLASSES According to the best approximation ratios known for them, NP-hard problems are classified into approximability classes. These classes create a kind of hierarchy in the class of the NP-hard problems. The best known among them (going from the pessimistic to the optimistic ones) are the following classes (for any standard-approximation class C, DC denotes the respective differential class). Exp-APX and Exp-DAPX. The classes of problems for which the best ratio known is exponential (or the inverse 3 of an exponential) with the size of their instance. The notorious member of Exp-APX is MIN TSP. On the other hand, no natural combinatorial optimization problem is still known to be in Exp-DAPX. Poly-APX and Poly-DAPX. The classes of problems for which the best ratio known is polynomial (or the inverse of a polynomial) with the size of their instance. MAX INDEPENDENT SET, MAX CLIQUE, MIN COLORING, etc., belong to Poly-APX. On the other hand, MAX INDEPENDENT SET, MAX CLIQUE, MIN VERTEX COVER, MIN SET COVER, etc., belong to Poly-DAPX. Log-APX and Log-DAPX. The classes of problems for which the best ratio known is an logarithm (or the inverse of an logarithm) of the size of their instance. MIN 3 Recall that when goal=max the approximation ratio is smaller than 1. V. Th. Paschos / An Overview on Polynomial Approximation of NP-hard Problems 7 and MIN DOMINATING SET are the most notorious representatives of Log-APX. On the other hand, no natural combinatorial problem is known to be in Log-DAPX. APX and DAPX. Here the “more optimistic” approximability classes start. APX and DAPX are the classes of problems approximable within the ratios that are fixed constants. MIN VERTEX COVER, MIN METRIC TSP 4 , BIN PACKING, MAX TSP, etc., belong to APX, while MIN TSP, MAX TSP, MIN COLORING, etc., belong to DAPX. PTAS and DPTAS. The classes of problems admitting polynomial time approximation schemata. A polynomial time approximation scheme, is a sequence of algorithms A ε achieving ratio 1 + ε , for every ε > 0 ( 1 − ε for maximization problems, or for the differential paradigm), in time which is polynomial with the size of the instance but exponential with 1/ε . MAX PLANAR INDEPENDENT SET 5 , MIN PLANAR VERTEX COVER 6 , MIN EUCLIDEAN TSP 7 , etc., are in PTAS. On the other hand, MAX INDEPENDENT SET, MIN PLANAR VERTEX COVER, BIN PACKING, etc., are known to belong to DPTAS. FPTAS and DFPTAS. The classes of problems admitting fully polynomial time approximation schemata. A fully polynomial time approximation scheme is a polynomial time approximation scheme that is, furthermore, polynomial with 1/ε . Also, KNAPSACK is in both FPTAS and DFPTAS. Let us also mention the existence of another approximability class denoted by 0DAPX (defined in [13]) that is meaningful only for the differential approximation paradigm. 0-DAPX is the class of problems for which any polynomial algorithm returns the worst solution in at least one of their instances. In other words, for problems in 0DAPX, the differential approximation ratio is equal to 0. MIN INDEPENDENT DOMINATING SET is known to be in 0-DAPX. Finally, let us note that, judging by the way the approximability classes are defined (i.e., as functions of the instance size), there is indeed a continuum of such classes. Figures 1 and 2 illustrate the approximability classes landscapes for standard and differential approximability paradigms, respectively. Dealing with the classes defined above, the following inclusions hold: SET COVER T These inclusions are strict unless P = NP. Indeed, for any of these classes, there are natural problems that belong to each of them but not to the immediately smaller ones. For instance, for the standard paradigm: 4 MIN TSP in complete graphs whose edge-weights verify the triangle-inequality. 5 MAX INDEPENDENT SET in planar graphs. 6 MIN VERTEX COVER in planar graphs. 7 MIN METRIC TSP in (0,1)-plane. 8 V. Th. Paschos / An Overview on Polynomial Approximation of NP-hard Problems Figure 1: Standard approximability classes (under the assumption P ≠ NP). Figure 2: Differential classes (under the assumption P ≠ NP). V. Th. Paschos / An Overview on Polynomial Approximation of NP-hard Problems 9 4 APPROXIMATION ALGORITHMS FOR SEVERAL NP-HARD PROBLEMS 4.1. Max independent set Given a graph G (V , E ) , the MAX INDEPENDENT SET problem consists of determining a maximum-size set V ′ ⊆ V so that, for every (u, v) ∈ V ′ × V ′ , (u , v) ∉ E . Let us first consider the integer-linear formulation of the MAX INDEPENDENT SET and its linear relaxation, denoted by MAX INDEPENDENT SET-R, where in the given graph G (V , E ) , A denotes its incidence matrix: The following seminal theorem, due to [57] gives a very interesting characterization for the basic optimal solution of (2). Theorem 1. ([57]). The basic optimal solution of MAX INDEPENDENT SET-R is semi-integral, i.e., it assigns values from {0,1,1/2} to the variables. If V0 , V1 and V1/2 are the subsets of V associated with 0, 1 et 1/2, respectively, then there exists a maximum independent set S * so that: V1 ⊆ S * * 2. V0 ⊆ V \ S 1. A basic corollary of Theorem 1 is that in order to solve MAX INDEPENDENT SET, one can first solve its linear relaxation MAX INDEPENDENT SET-R (this can be done in polynomial time [3, 37, 48, 69]) and store V1 and then solve the MAX INDEPENDENT SET in some way in G[V1/2 ] , i.e., the subgraph of G induced by V1/2 . Indeed, the solution of the MAX INDEPENDENT SET-R provides sets V0 , V1 and V1/2 that form a partition of V . Furthermore, by the constraint set of this program, edges can exist into V0 and V1/2 and between V1 and V0 and V0 and V1/2 , but not between V1 and V1/2 (see also Figure 3 where thick lines indicate the possible existence of edges between vertex-sets). So, the union of V1 (that is an independent set per se) and of an independent set of G[V1/2 ] is an independent set for the whole of G . Let us now consider the following algorithm, due to [43], denoted by IS: 1. solve MAX INDEPENDENT SET-R in order to determine V0 , V1 et V1/2 ; 10 V. Th. Paschos / An Overview on Polynomial Approximation of NP-hard Problems 2. color G[V1/2 ] with at most Δ (G[V1/2 ]) colors (where, for a graph G , Δ(G ) 3. denotes its maximum degree) using the algorithm by [53]; let Ŝ be the largest color output S = V ∪ Sˆ 1 Figure: 3: A graph G and the possibility of existence of edges between sets V0 , V1 and V1/2 computed by the solution of MAX INDEPENDENT SET-R. Theorem 2.The algorithm IS achieves the approximation ratio 2/Δ (G ) for the problem. Proof. Let us first recall that the vertices of a graph G can be feasibly colored 8 with at most Δ(G ) colors in polynomial time ([53]). This result is, in fact, the constructive proof of an existential theorem about such coloring originally stated by [18]. MAX INDEPENDENT SET Fix a maximum independent set S * of G that contains V1 (by item 1 in Theorem 1 this is always possible). Since Ŝ is the largest of the at most Δ (G[V1/2 ]) colors (independent sets) produced in step 2 of Algorithm IS, its size satisfies: Sˆ ≥ V1/2 (3) Δ ( G [V1/2 ]) The size of S returned by the algorithm at step 3 is given by: (3) m( S , G ) =| S |= V1 + Sˆ ≥ V1 + 8 On the given graph V1/2 Δ ( G [V1/2 ]) ≥ V1 + V1/2 Δ (G ) (4) G (V , E ) , a coloring of V consists of coloring the vertices of V in such a way that no adjacent vertices receive the same color; in other words, a color has to be an independent set and a coloring of V is, indeed, a partition of V into independent sets. V. Th. Paschos / An Overview on Polynomial Approximation of NP-hard Problems 11 * Finally, denote by S1/2 a maximum independent set in G[V1/2 ] . Observe that the value of the optimal solution for MAX INDEPENDENT SET-R in G[V1/2 ] is equal to V1/2 /2 . Since MAX INDEPENDENT SET is a maximization problem, the objective value of (integer) MAX INDEPENDENT SET is bounded above by the objective value of (continuous) MAX INDEPENDENT SET-R. Hence: * S1/2 ≤ V1/2 (5) 2 Denote by α (G ) , the size of S * . Then, obviously, the following holds: V1/2 (5) * opt (G ) = S * = V1 + S1/2 ≤ V1 + (6) 2 Putting together (4) and (6) we get the claimed ratio and complete the proof of the theorem. A slight improvement of the ratio claimed in Theorem 2 appears in [63]. An immediate corollary of Theorem 2 is that MAX INDEPENDENT SET belongs to Poly-APX. Also, since the value ω (G ) of the worst solution to the problem is 0 (i.e., we can consider the empty vertex-set as a feasible MAX INDEPENDENT SET solution), standard- and differential-approximation ratios coincide. So, MAX INDEPENDENT SET belongs to Poly-DAPX also. Finally, let us note that the strongest approximation results known for this problem are the following: ƒ MAX INDEPENDENT SET is asymptotically approximable (i.e., for large Δ(G ) within ratio k/Δ (G ) , for every fixed constant k ([28, 64]); 2 ƒ is approximable within ratio O(log n/n) ([39]) and within O(log n/Δ (G ) loglog n) ([29]); ƒ is inapproximable within better than O (nε −1 ) for any ε > 0 , unless P = NP ([42]). MAX INDEPENDENT SET MAX INDEPENDENT SET 4.2. Min set cover Given a ground set C = {c1 ,… , cn } and a collection S = {S1 ,… , S m } ⊂ 2C of subsets of C , MIN SET COVER consists of determining a minimum-size sub-collection S' ⊆ S that covers C , i.e., such that ∪ S∈S' S = C . Let us consider the following natural greedy algorithm for MIN SET COVER denoted by GREEDYSC: 1. set: S' = S' ∪ {S} , where S ∈S ∈S {| Si |} ( S' is assumed to be empty at the i 2. beginning of the algorithm); update I ( S , C ) by setting: S = S \ {S } , C = C \ S and, for S j ∈ S , Sj = Sj \ S ; 3. 4. repeat steps 1 and 2 until C = ∅ ; output S' . 12 V. Th. Paschos / An Overview on Polynomial Approximation of NP-hard Problems This algorithm has been independently analyzed by [46, 52]. Its version for where we ask for determining a set cover of minimum total weight has been analyzed by [20]. It is easy to see that Algorithm GREEDYSC runs in polynomial time. Theorem 3. The standard-approximation ratio of Algorithm GREEDYSC is bounded above by 1 + ln Δ , where Δ = max S∈S{| S |} . Proof. Denoted by I i ( Si , Ci ) , the surviving instance in the first moment residual cardinalities of sets in S are at most i ; denoted by m( I i , S') the number of sets of residual cardinality i placed in S' and note that m( I Δ , S') = m( I , S') . Following these notations: WEIGHTED MIN SET COVER (7) CΔ = C Δ m ( I , S') = ∑m ( I i , S') (8) i =1 For i = 1,… , Δ , we have the following Δ -line equation-system: i Ci = ∑k × m ( I k , S') (9) k =1 where any of the above equations expresses the facts that: (1) any time a set S is chosen to be part of S' , Algorithm GREEDYSC removes from C the elements of S and (2) for any i , the remaining ground set Ci to be covered, is covered by sets of cardinality at most equal to i chosen later by the algorithm. Multiplying the Δ th line of (9) by 1/Δ and, for the other lines, line i by 1/(i (i + 1)) and taking into account (7), (8) and the fact that: 1 1 1 = − i (i + 1) i i + 1 we finally obtain: ⎛ Δ −1 Ci ⎞ | C | Δ = ∑m ( I i , S') = m ( I , S') ⎜∑ ⎟+ i =1 ⎝ i =1 i (i + 1) ⎠ Δ (10) Consider now an optimal solution S * of I ( S , C ) and let Si* be an optimal solution for I i ( Si , Ci ) , i = 1,… , Δ . Elements of S * covering Ci are always present and form a feasible solution for I i . Therefore: Ci ≤ i × opt ( I i ) (12)