Giorgio Ausiello
email: ausiello@dis.uniroma1.it

Vangelis Th Paschos
email: paschos@lamsade.dauphine.fr

Differential approximation *

In this paper, we survey the fundamentals of the differential approximation theory, as well as some operational and structural results. * Preliminary version of Chapter 13 to appear in T. Gongalez (ed.), Approximation algorithms and metaheuristics, Taylor and Francis.

1 With respect to the inclusion.

Introduction

In this chapter, we use the notations introduced in chapter R-7. Also, given an approximation algorithm A for an NPO problem Π, we denote by m A (x, y), the value of the solution y computed by A on instance x of Π. When clear from the context, reference to A will be omitted.

Very frequently, the commonly used approximation measure (called standard approximation ratio in what follows) may not be very meaningful, in particular if the ratio of m(x, y w ), the worst solution's value for x, to opt(x) is already bounded (above, if goal(Π) = min, below, otherwise). Consider, for instance, the seminal maximal matching algorithm for min vertex cover (the definitions of the most of the problems dealt in this chapter can be found in [START_REF] Ausiello | Complexity and approximation[END_REF][START_REF] Garey | Computers and intractability. A guide to the theory of NP-completeness[END_REF]; also, for graph-theoretic notions, the interested reader can be referred to [START_REF] Berge | Graphs and hypergraphs[END_REF]), that achieves approximation ratio 2 for this problem. There, given a graph G(V, E), a maximal 1 matching M of G is computed and the endpoints of the edges in M are added in the solution for min vertex cover. If M is perfect (almost any graph, even relatively sparse, admits a perfect matching [START_REF] Bollobás | Random graphs[END_REF]), then the whole of V has been included in the cover built, while an optimal cover contains at least a half of V . So, the absolutely worst solution (that one could compute without using any algorithm) achieves in most cases approximation ratio 2.

The remark above is just one drawback of the standard approximation ratio. Several other drawbacks have been also observed, for instance, the artificial dissymmetry between "equivalent" minimization and maximization problems (for example, max cut and min clustering, see [START_REF] Sahni | P-complete approximation problems[END_REF]) introduced by the standard approximation ratio. The most blatant case of such dissymmetry is the one appearing when dealing with the approximation of min vertex cover and max independent set (given a graph, a vertex cover is the complement of an independent set with respect to the vertex set of the graph). In other words, using linear programming vocabulary, the objective function of the former is an affine transformation of the objective function of the latter.

This equivalence under such simple affine transformation is not reflected to the approximability of these problems: the former is approximable within constant ratio, in other words it is in APX (see [START_REF] Ausiello | Complexity and approximation[END_REF][START_REF] Th | Complexité et approximation polynomiale[END_REF] for definition of the approximability classes dealing with the standard paradigm; the ones of the differential paradigm are defined analogously), while the latter is inapproximable within ratio Ω(n ǫ-1 ), for any ǫ > 0 (see [START_REF] Håstad | Clique is hard to approximate within n 1-ǫ[END_REF]). In other words, the standard approximation ratio is unstable under affine transformations of the objective function.

In order to remedy to these phenomena, several researchers have tried to adopt alternative approximation measures not suffering from these inconsistencies. One of them is the ratio δ(x, y) = (ω(x)m(x, y))/(ω(x)opt(x)), called differential ratio in the sequel, where ω(x) is the value of a worst solution for x, called worst value. It will be formally dealt in the next sections. It has been used rather punctually and without following a rigorous axiomatic approach until the paper [START_REF] Demange | On an approximation measure founded on the links between optimization and polynomial approximation theory[END_REF] where such an approach is introduced. To our knowledge, differential ratio is introduced in [START_REF] Ausiello | On the structure of combinatorial and structure preserving reductions[END_REF] in 1977, and [START_REF] Ausiello | Structure preserving reductions among convex optimization problems[END_REF][START_REF] Aiello | Computational complexity: the problem of approximation[END_REF][START_REF] Zemel | Measuring the quality of approximate solutions to zero-one programming problems[END_REF] are, to our knowledge, the most notable cases in which this approach has been applied. It is worth noting that in [START_REF] Zemel | Measuring the quality of approximate solutions to zero-one programming problems[END_REF], a weak axiomatic approach is also presented.

Finally, let us note that several other authors that have also recognized the methodological problems implied by the standard ratio, have proposed other alternative ratios. It is interesting to remark that the main such ratios are very close, although with some small or less small differences, to the differential ratio. For instance, in [START_REF] Cornuejols | Location of bank accounts to optimize float: an analytic study of exact and approximate algorithms[END_REF], for studying max tsp, it is proposed the ratio d(x, y, z r ) = |opt(x)m(x, y)|/|opt(x)z r |, where z r is a positive value computable in polynomial time, called reference-value. It is smaller than the value of any feasible solution of x, hence smaller than ω(x) (for a maximization problem a worst solution is the one of the smallest feasible value). The quantities |opt(x)m(x, y)| and |opt(x)z r | are called deviation, and absolute deviation, respectively. The approximation ratio d(x, y, z r ) depends on both x and z r , in other words, there exist a multitude of such ratios for an instance x of an NPO problem, one for any possible value of z r . Consider a maximization problem Π and an instance x of Π. Then, d(x, y, z r ) is increasing with z r , so, d(x, y, z r ) d(x, y, ω(x)). In fact, in this case, for any reference value z r : r(x, y)

1d(x, y, z r ) 1d(x, y, ω(x)) = δ(x, y), where r denotes the standard-approximation ratio for Π. When ω(x) is computable in polynomial time, d(x, y, ω(x)) is the smallest (tightest) over all the d-ratios for x. In any case, if for a given problem, one sets z r = ω(x), then d(x, y, ω(x)) = 1δ(x, y) and both ratios have the natural interpretation of estimating the relative position of the approximate solution-value in the interval worst solutionvalue -optimal value.

Towards a new approximation paradigm

The differential approximation ratio

In [START_REF] Demange | On an approximation measure founded on the links between optimization and polynomial approximation theory[END_REF], it is undertaken the task of adopting, in an axiomatic way, an approximation measure founded on both intuitive and mathematical links between optimization and approximation. It is claimed there that a "consistent" ratio must be order preserving (i.e., the better the solution the better the approximation ratio achieved) and stable under affine transformation of the objective function. Furthermore, it is proved that no ratio function of two parameters -for example, m, opt -can fit this latter requirement. Hence it is proposed what will be called differential approximation ratio2 in what follows. Problems related by affine transformations of their objective functions are called affine equivalent.

Consider an instance x of an NPO problem Π and a polynomial time approximation algorithm A for Π, the differential approximation ratio δ A (x, y) of a solution y computed by A in x is defined by:

δ A (x, y) = (ω(x) -m A (x, y)) (ω(x) -opt(x))
where ω(x) is the value of a worst solution for x, called worst value. Note that for any goal, δ A (x, y) ∈ [0, 1] and, moreover, the closer δ A (x, y) to 1, the closer m A (x, y) to opt(x). By definition, when ω(x) = opt(x), i.e., all the solutions of x have the same value, then the approximation ratio is 1. Notice that, m A (x, y)) = δ A (x, y)opt(x) + (1δ A (x, y))ω(x). So, differential approximation ratio measures how an approximate solution is placed in the interval between ω(x) and opt(x).

We note that the concept of the worst solution has a status similar to the one of the optimal solution. It depends on the problem itself and is defined in a non-constructive way, i.e., independently of any algorithm that could build it. The following definition for worst solution is proposed in [START_REF] Demange | On an approximation measure founded on the links between optimization and polynomial approximation theory[END_REF].

Definition 1. Given an NPO problem Π = (I, Sol, m, goal), a worst solution of an instance x of Π is defined as an optimal solution of a new problem Π = (I, Sol, m, goal), i.e., of a NPO problem having the same sets of instances and of instances and of feasible solutions and the same value-function as Π but its goal is the inverse of the one of Π, i.e., goal = min if goal = max and vice-versa.

Example 1. The worst solution for an instance of min vertex cover or of min coloring is the whole vertex-set of the input-graph, while for an instance of max independent set the worst solution is the empty set. On the other hand, if one deals with an max independent set with the additional constraint that a feasible solution has to be maximal with respect to inclusion, the worst solution of an instance of this variant is a minimum maximal independent set, i.e., an optimal solution of a very well-known combinatorial problem, the min independent dominating set. Also, the worst solution for min tsp is a "heaviest" Hamiltonian cycle of the input-graph, i.e., an optimal solution of max tsp, while for max tsp the worst solution is the optimal solution of a min tsp. The same holds for the pair max sat, min sat.

From Example 1, one can see that, although for some problems a worst solution corresponds to some trivial input-parameter and can be computed in polynomial time (this is, for instance, the case of min vertex cover, max independent set, min coloring, etc.), there exist a lot of problems for which, determining a worst solution is as hard as determining an optimal one (as for min independent dominating set, min tsp, max tsp, min sat, max sat, etc.). Remark 1 . Consider the pair of affine equivalent problems min vertex cover, max independent set and an input-graph G(V, E) of order n. Denote by τ (G) the cardinality of a minimum vertex cover of G and by α(G), the stability number of G. Obviously, τ (G) = n-α(G).

Based upon what has been discussed above, the differential ratio of some vertex cover

C of G is δ(G, C) = (n -|C|)/(n -τ (G)). Since the set S = V \ C is an independent set of G, its differential ratio is δ(G, S) = (|S| -0)/(α(G) -0) = (n -|C|)/(n -τ (G)) = δ(G, C).
As we have already mentioned, the differential ratio, although without systematic use or axiomatic approach, has been used at several times by many authors, before and after [START_REF] Demange | On an approximation measure founded on the links between optimization and polynomial approximation theory[END_REF]. They use it in several contexts going from mathematical (linear or non-linear) programming [START_REF] Bellare | The complexity of approximating a nonlinear program[END_REF][START_REF] Nemirovski | Problem complexity and method efficiency in optimization[END_REF][START_REF] Vavasis | Approximation algorithms for indefinite quadratic programming[END_REF] to pure combinatorial optimization [START_REF] Ausiello | Structure preserving reductions among convex optimization problems[END_REF][START_REF] Ausiello | Lattice-theoretical ordering properties for NPcomplete optimization problems[END_REF][START_REF] Aiello | Computational complexity: the problem of approximation[END_REF][START_REF] Hassin | z-approximations[END_REF][START_REF] Hassin | Maximizing the number of unused colors in the vertex coloring problem[END_REF], or they disguise differential approximation of a problem to standard approximation of affine transformations of it. For instance, in order to study differential approximation of bin packing, one can deal with standard approximation of the problem of maximizing the number of unused bins; for min coloring, the affinely equivalent problem is the one of maximizing the number of unused colors, for min set cover, this problem is the one of maximizing the number of unused sets, etc.

Asymptotic differential approximation ratio

In any approximation paradigm, the notion of asymptotic approximation (dealing, informally, with a class of "interesting" instances) is pertinent. In the standard paradigm, the asymptotic approximation ratio is defined on the hypothesis that the interesting (from an approximation point of view) instances of the simple problems are the ones whose values of the optimal solutions tend to ∞ (because, in the opposite case3 , these problems, called simple ( [START_REF] Paz | Non deterministic polynomial optimization problems and their ap[END_REF]), are polynomial). In the differential approximation framework on the contrary, the size (or the value) of the optimal solution is not always a pertinent hardness criterion (see [START_REF] Demange | Asymptotic differential approximation ratio: definitions, motivations and application to some combinatorial problems[END_REF] for several examples about this claim). Henceforth, in [START_REF] Demange | Asymptotic differential approximation ratio: definitions, motivations and application to some combinatorial problems[END_REF], another hardness criterion, the number σ(x) of the feasible values of x, has been used to introduce the asymptotic differential approximation ratio. Under this criterion, the asymptotic differential approximation ratio of an algorithm A is defined as

δ ∞ A (x, y) = lim k→∞ inf x σ(x) k ω(x) -m(x, y) ω(x) -opt(I) (1)
Let us note that σ(x) is motivated by, and generalizes, the notion of the structure of the instance introduced in [START_REF] Ausiello | Structure preserving reductions among convex optimization problems[END_REF]. We also notice that the condition σ(x) k characterizing "the sequence of unbounded instances" (or "limit instances") cannot be polynomially verified 4 . But in practice, for a given problem, it is possible to directly interpret condition σ(x)

k by means of the parameters ω(x) and opt(x) (note that σ(x) is not a function of these values). For example, for numerous cases of discrete problems, it is possible to determine, for any instance x, a step π(x) defined as the least variation between two feasible values of x. For example, for bin packing,

π(x) = 1. Then, σ(x) (ω(x) -opt(x)) π(x) + 1 Therefore, from (1)
:

δ ∞ A (x, y) lim k→∞ inf x ω(x)-opt(x) π(x) k-1 ω(x) -m(x, y) ω(x) -opt(x)
Whenever π can be determined, condition (ω(x)opt(x))/π(x) k-1 can be easier to evaluate than σ(x) k, and in this case, the former condition is used (this is not senseless since we try to bound below the ratio). The adoption of σ(x) as hardness criterion can be motivated by considering a class of problems, called radial problems in [START_REF] Demange | Asymptotic differential approximation ratio: definitions, motivations and application to some combinatorial problems[END_REF], that includes many well-known combinatorial optimization problems, as bin packing, max independent set, min vertex cover, min coloring, etc. Informally, a problem Π is radial if, given an instance x of Π and a feasible solution y for x, one can, in polynomial time, on the one hand, deteriorate y as much as one wants (up to finally obtain a worst-value solution) and, on the other hand, greedily improve y in order to obtain (always in polynomial time) a sub-optimal solution (eventually the optimal one). Definition 2. A problem Π = (I, Sol, m, goal) is radial if there exist three polynomial algorithms ξ, ψ and ϕ such that, for any x ∈ I:

1. ξ computes a feasible solution y (0) for x;

2. for any feasible solution y of x strictly better (in the sense of the value) than y (0) , algorithm ϕ computes a feasible solution ϕ(y) (if any) such that m(x, ϕ(y)) is strictly worse than m(x, y) (i.e., m(x, ϕ(y)) > m(x, y), if goal(Π) = min and m(x, ϕ(y)) < m(x, y), if goal(Π) = max);

3. for any feasible solution y of x with value strictly better than m(x, y (0) ), there exists k ∈ N such that ϕ k (y) = y (0) (where ϕ k denotes the k-times iteration of ϕ);

4. for a solution y such that, either y = y (0) , or y is any feasible solution of x with value strictly better than m(x, y (0) ), ψ(y) computes the set of ancestors of y, defined by:

ψ(y) = ϕ -1 ({y}) = {z : ϕ(z) = y}
(this set being eventually empty) .

Let us note that the class of radial problems includes in particular the well-known class of hereditary problems for which any subset of a feasible solution remains feasible. In fact, for an hereditary (maximization) problem, a feasible solutions y is a subset of the input-data, for any instances x, y (0) = ∅ and for any other feasible solution y, ϕ(y) is just obtained from y by removing a component of y. The hereditary notion deals with problems for which a feasible solution is a subset of the input-data, while the radial notion allows problems for which solutions are also second-order structures of the input-data.

Example 2. We show that bin packing is radial. Consider a list L of n rational numbers; then,

• one can easily compute a solution B (0) for bin packing consisting of putting an item per bin (so B (0) is a collection of n one-item bins); so, condition 1 is satisfied;

• given a feasible solutio B, one can deteriorate it by removing an item a from a bin of B containing at least two items and by putting a in a new (unused) bin; so, condition 2 is satisfied;

• one can continue this deterioration of B by repeatedly executing the above item until solution B (0) is obtained; so, condition 3 is satisfied;

• we show finally that condition 4 of definition 2 is also satisfied; consider either solution B (0) or any other feasible solution B

one can obtain better solutions by iteratively trying to empty some bins of B (0) (or B), i.e., by considering an single-item bin and by trying to place its item in another nonempty bin of B (0) (or B);

one can continue this procedure as far as it leads to smaller feasible bin packingsolutions;

moreover, if one guesses successfully the single items to be moved, then one could obtain even an optimal bin packing-solution;

In all, bin packing satisfies all the items of Definition 2.

Proposition 1. ( [START_REF] Demange | Asymptotic differential approximation ratio: definitions, motivations and application to some combinatorial problems[END_REF]) Let κ be a fixed constant and consider a radial problem Π such that, for any instance x of Π of size n, σ(x) κ. Then, Π is polynomial.

Differential approximation results for some optimization problems

In general, no systematic way allows to link results obtained in standard and differential approximation paradigms when dealing with minimization problems. In other words, there is no evident transfer of positive or inapproximability results from one framework to the other one. Hence, a "good" differential approximation result does not signify anything for the behavior of the approximation algorithm studied, or of the problem itself, when dealing with the standard framework, and vice-versa. Things are somewhat different for maximization problems with positive solution-values. In fact, considering an instance x of a maximization problem Π and a solution y ∈ Sol(x) that is a δ-differential approximation, we immediately get:

m(x, y) -ω(x) opt(x) -ω(x) δ =⇒ m(x, y) opt(x) δ + (1 -δ) ω(x) opt(x) ω(x) 0 =⇒ m(x, y) opt(x) δ
So, positive results are transferred from differential to standard approximation, while transfer of inapproximability thresholds is done in the opposite direction.

Fact 1. Approximation of a maximization NPO problem Π within differential-approximation ratio δ, implies its approximation within standard-approximation ratio δ.

Fact 1 has interesting applications. The most immediate of them deals with the case of maximization problems with worst-solution values 0. There, standard and approximation ratios coincide. In this case, the differential paradigm inherits the inapproximability thresholds of the standard one. For instance, the inapproximability of max independent set within n ǫ-1 , for any ǫ > 0 ( [START_REF] Håstad | Clique is hard to approximate within n 1-ǫ[END_REF]), becomes a result shared from both of the paradigms. Furthermore, since max independent set and min vertex cover are affine equivalent, henceforth differentially equi-approximable, the negative result for max independent set is shared, in the differential paradigm, by min vertex cover.

Corollary 1. Both max independent set and min vertex cover are inapproximable within differential ratios n ǫ-1 , for any ǫ > 0, unless P = NP.

Notice that differential equi-approximability of max independent set and min vertex cover makes that, in this framework the latter problem is not constant approximable but inherits also the positive standard approximation results of the former one ( [START_REF] Demange | Improved approximations for maximum independent set via approximation chains[END_REF][START_REF] Demange | Improved approximations for weighted and unweighted graph problems[END_REF][START_REF] Halldórsson | Approximations of weighted independent set and hereditary subset problems[END_REF]).

In what follows in this section, we mainly focus ourselves on three well-known NPO problems: min coloring, bin packing, tsp in both minimization and maximization variants, ant min multiprocessor scheduling. As we will see, approximabilities of min coloring and min tsp are radically different from the standard paradigm (where these problems are very hard) to the differential one (where they become fairly well-approximable). For the two first of them, differential approximability will be introduced by means of more general problem that encompasses both min coloring and bin packing, namely, the min hereditary covering. min hereditary covering@min hereditary covering

min hereditary cover

Let π be a non-trivial hereditary property 5 on sets and C a ground set. A π-covering of C is a collection S = {S 1 , S 2 , S q } of subsets of C (i.e. a subset of 2 C ), any of them verifying π and such that ∪ q i=1 S i = C. Then, min hereditary cover consists, given a property π, a ground set C and a family S including any subset of C verifying π, of determining a π-covering of minimum size. Observe that, by definition of the instances of min hereditary cover singletons of the ground sets are included in any of them and are always sufficient to cover C. Henceforth, for any instance x of the problem, ω(x) = |C|.

It is easy to see that, given a π-covering, one can yield a π-partition (i.e., a collection S where for any S i , S j ∈ S, S i ∩ S j = ∅) of the same size, by greedily removing duplications of elements of C. Henceforth, min hereditary cover or min hereditary partition are, in fact, the same problem. min hereditary cover has been introduced in [START_REF] Monnot | Critical families of instances and polynomial approximation[END_REF] and revisited in [START_REF] Hassin | z-approximations[END_REF] under the name min cover by independent sets. Moreover, in the former paper, using a clever adaptation of the local improvement methods of [START_REF] Halldórsson | Approximating k-set cover and complementary graph coloring[END_REF], a differential ratio 3/4 for min hereditary cover has been proposed. Based upon [START_REF] Duh | Approximation of k-set cover by semi-local optimization[END_REF], this ratio has been carried to 289/360 by [START_REF] Hassin | z-approximations[END_REF].

A lot of well-known NPO problems are instantiations of min hereditary cover. For instance, min coloring becomes an min hereditary cover-problem, considering as ground set the vertices of the input-graph and as set-system, the set of the independent sets6 of this graph. The same holds for the partition of the covering of a graph by subgraphs that are planar, or by degree-bounded subgraphs, etc. Furthermore, if any element of C is associated with a weight and a subset S i of C is in S if the total weight of its members is at most 1, then one recovers bin packing.

In fact, an instance of min hereditary cover can be seen as a virtual instance of min set cover, even if there is no always need to explicit it. Furthermore, the following general result links min k-set cover (the restriction of min set cover to subsets of cardinality at most k) and min hereditary cover (see [START_REF] Th | Polynomial approximation and graph coloring[END_REF] for its proof in the case of min coloring; it can be immediately seen that its extension to the general min hereditary cover is immediate).

Theorem 1. If min k-set cover is approximable in polynomial time within differential approximation ratio δ, then min hereditary cover is approximable in polynomial time within differential-approximation ratio min{δ, k/(k + 1)}.

min coloring

min coloring has been systematically studied in the differential paradigm. Sub-sequent papers ( [START_REF] Demange | Approximation results for the minimum graph coloring problem[END_REF][START_REF] Demange | Differential approximation algorithms for some combinatorial optimization problems[END_REF][START_REF] Hassin | Maximizing the number of unused colors in the vertex coloring problem[END_REF][START_REF] Halldórsson | Approximating discrete collections via local improvements[END_REF][START_REF] Halldórsson | Approximating k-set cover and complementary graph coloring[END_REF][START_REF] Tzeng | Three-quarter approximation for the number of unused colors in graph coloring[END_REF][START_REF] Duh | Approximation of k-set cover by semi-local optimization[END_REF]) have improved its differential approximation ratio from 1/2 to 289/360. This problem is also a typical example of a problem that behaves in completely different ways when dealing with the standard or the differential paradigms. Indeed, dealing with the former one, min coloring is inapproximable within ratio n 1-ǫ , for any ǫ > 0, unless problems in NP can be solved by slightly super-polynomial deterministic algorithms (see [START_REF] Ausiello | Complexity and approximation[END_REF]).

As we have seen just previously, given a graph G(V, E), min coloring can be seen as a min hereditary cover-problem considering C = V and taking for S the set of the independent sets of G. According to Theorem 1 and to [START_REF] Duh | Approximation of k-set cover by semi-local optimization[END_REF], where min 6-set cover is proved approximable within differential ratio 289/360, one can derive that also is approximable within differential ratio 289/360. Notice that any result for min coloring holds also for the minimum vertexpartition (or covering) into cliques problem since an independent set in some graph G becomes a clique in the complement Ḡ of G (in other words this problem is also an instantiation of min hereditary cover). Furthermore, in [START_REF] Demange | Approximation results for the minimum graph coloring problem[END_REF][START_REF] Demange | Differential approximation algorithms for some combinatorial optimization problems[END_REF], a differential ratio preserving reduction is devised between minimum vertex-partition into cliques and minimum edge-partition (or covering) into cliques. So, as in the standard paradigm, all these three problems have identical differential approximation behavior.

Finally, it is proved in [START_REF] Bazgan | Completeness in standard and differential approximation classes: Poly-(D)APX-and (D)PTAS-completeness[END_REF] that min coloring is DAPX-complete (see also Section 4.3.1); consequently, unless P = NP, it cannot be solved by polynomial time differential-approximation schemata. This derives immediately that neither min hereditary cover belongs to DPTAS, unless P = NP.

bin packing

We now deal with another very well-known NPO problem, the bin packing. According to what has been discussed just above, bin packing being a particular case of min hereditary cover, it is approximable within differential ratio 289/360. In what follows in this section, we refine this result by first presenting an approximation preserving reduction transforming any standard approximation ratio ρ into differential approximation ratio δ = 2ρ. Then, based upon this reduction we show that bin packing can be solved by a polynomial time differential approximation schema; in other words, bin packing ∈ DPTAS. This result draws another, although less dramatical than the one in Section 3.1.1, difference between standard and differential approximation. In the former paradigm, bin packing is solved by an asymptotical polynomial time approximation schema, more precisely within standard-approximations ratio 1 + ǫ + (1/opt(L)), for any ǫ > 0 ( [START_REF] De | Bin packing can be solved within 1 + ǫ in linear time[END_REF]), but it is NP-hard to approximate it by a "real" polynomial time approximation schema ( [START_REF] Garey | Computers and intractability. A guide to the theory of NP-completeness[END_REF]).

Consider a list L = {x 1 , . . . , x n }, instance of bin packing, assume, without loss of generality, that items in L are rational numbers ranged in decreasing order and fix an optimal solution B * of L. Observe that ω(L) = n. For the purposes of this section, a bin i will be denoted either by b i , or by explicit listing of the numbers placed in it; finally, any solution will be alternatively represented as union of its bins.

Lemma 1. ([25]

) Let k * be the number of bins in B * that contain a single item. Then, there exists an optimal solution B * = {x 1 } ∪ . . . ∪ {x k * } ∪ B * 2 for L, where any bin in B * 2 contains at least two items. Furthermore, for any optimal solution B = {b j : j = 1, . . . , opt(L)} and for any set J ⊂ {1, . . . , opt(L)}, the solution B j = {b j ∈ B : j ∈ J} is optimal for the sub-list L j = ∪ j∈J b j .

Theorem 2. From any algorithm achieving standard approximation ratio ρ for bin packing, can be derived an algorithm achieving differential approximation ratio δ = 2ρ. Sketch of proof. Consider Algorithm SA achieving standard approximation ratio ρ for bin packing, denote by SA(L) the solution computed by it, when running on an instance L (recall that L is assumed ranged in decreasing order), and run the following algorithm, denoted by DA in the sequel, which uses SA as sub-procedure: ). Putting all this together, we get:

1. for k = 1 to n set: L k = {x k+1 , . . . , x n }, B k = {x 1 } ∪ . . . ∪ {x k } ∪ SA(L k );
δ DA (L, B) = n -|B| n -opt(L) |L k * | -|B k * | |L k * | -opt (L k * ) 2 -ρ q.e.d.
In what follows, denote by EXHAUSTIVE an exhaustive-search algorithm for bin packing, by SA any polynomial algorithm approximately solving bin packing within (fixed) constant standard-approximation ratio ρ SA 1, by ASCHEMA(ǫ) the asymptotic polynomial time standardapproximation schema of [START_REF] De | Bin packing can be solved within 1 + ǫ in linear time[END_REF], parameterized by ǫ > 0, and consider the following algorithm, denoted by EBP(L,η), parameterized by η ∈ {0, . . . , n} (L is always assumed ranged in decreasing order):

1. for k = nη + 1, . . . , n build list L k-1 where L k-1 is as in Step 1 of Algorithm DA;

for any list

L i computed in Step 1 above, set B i = {{x} : x ∈ L \ L i } ∪ EXHAUSTIVE(L i );
3. return B the smallest of the solutions computed in Step 2.

Algorithm EBP(L,η) obviously computes a feasible bin packing-solution for L in polynomial time whenever η is a fixed constant.

Lemma 2. ([25]) Assume a list L such that |L k * +1 | η.
Then, algorithm EBP(L,η) exactly solves bin packing in L in polynomial time when µ is a fixed constant.

Lemma 3 . ([25]

) Fix a polynomial time approximation algorithm SA for bin packing that guarantees standard-approximation ratio ρ SA , let ǫ be any fixed positive constant and L be an instance of bin packing (ranged in decreasing order). Assume that L is such that

|L k * +1 | 2(ρ SA -1 + ǫ)/ǫ 2 . Then, if opt(L k * +1 ) ǫ|L k * +1 |/(ρ SA -1 + ǫ)
, the approximation ratio of algorithm DA, when calling SA as sub-procedure, is δ 1ǫ; on the other hand, if opt(L k * +1 ) ǫ|L k * +1 |/(ρ SA -1 + ǫ), then the approximation ratio of algorithm DA, when calling ASCHEMA(ǫ/2) as sub-procedure, is δ 1ǫ.

Fix any polynomial algorithm A for bin packing with standard-approximation ratio ρ and consider the following algorithm for bin packing, denoted by DSCHEMA:

1. fix a constant ǫ > 0 and set η = ⌊2(ρ -1 + ǫ)/ǫ 2 ⌋; 2. run EBP and DA both with A and ASCHEMA(ǫ/2), respectively as sub-procedures on L; Let us note that, as we will see in Section 4.4, bin packing is DPTAS-complete; consequently, unless P = NP it is inapproximable by fully polynomial time differential-approximation schemata. Inapproximability of bin packing by such schemata has independently been shown also in [START_REF] Demange | Improved approximations for maximum independent set via approximation chains[END_REF].

Travelling salesman problems

min tsp is one of the most paradigmatic problems in combinatorial optimization and one of the hardest one to approximate. Indeed, unless P = NP, no polynomial algorithm can guarantee, on an edge-weighted complete graph of size n when no restriction is imposed to the edge-weights, standard-approximation ratio O(2 p(n) ), for any polynomial p. As we will see in this section things Theorem 5. min tsp, max tsp, min metric tsp and max metric tsp are differentially 2/3-approximable.

A very famous restrictive version of min metric tsp is the min tsp12, where edge-weights are all either 1, or 2. In [START_REF] Monnot | Differential approximation results for the traveling salesman problem with distances 1 and 2[END_REF], it is proved that this version (as well as, obviously, max tsp12) is approximable within differential ratio 3/4.

min multiprocessor scheduling

We now deal with a classical scheduling problem, the min multiprocessor scheduling ( [START_REF] Hochbaum | Using dual approximation algorithms for scheduling problems: theoretical and practical results[END_REF]), where we are given n tasks t 1 , . . . , t n with (execution) time lengths l(t j ), j = 1, . . . , n, polynomial n, that have to be executed on m processors, and the objective is to partition these tasks on the processors in such a way that the occupancy of the busiest processor is minimized. Observe that the worst solution is the one where all the task are executed in the same processor; so, given an instance x of min multiprocessor scheduling, ω(x) = n j=1 l(t j ). A solution y of this problem will be represented as a vector in {0, 1} mn , the non-zero components y i j of which correspond to the assignment of task j to processor i.

Consider a simple local search algorithms that starts from some solution and improves it upon any change of the assignment of a single task from one processor to another one. Then the following result can be obtained ( [START_REF] Monnot | Optima locaux garantis pour l'approximation différentielle[END_REF]). Theorem 6 . min multiprocessor scheduling is approximable within differential ratio m/(m + 1). Sketch of proof. Assume that both tasks and processors are ranged with decreasing lengths and occupancies, respectively. Denote by l(p i ), the total occupancy of processor p i , i = 1, . . . , m. Then:

opt(x) l (t 1 ) l (p 1 ) = n j=1 y 1 j l (t j ) = max i=1,...,m    l (p i ) = n j=1 y i j l (t j )
   Denote, w.l.o.g., by 1, . . . , q, the indices of the tasks assigned to p 1 . Since y is a local optimal, it verifies, for i = 2, . . . , m, j = 1, . . . q: l(t j ) + l(p i ) l(p 1 ). We can assume q 2 (on the contrary y is optimal). Then, adding the preceding expression for j = 1, . . . , q, we get: l(p i ) l(p 1 )/2. Also, adding l(p 1 ) with the preceding expression for l(p i ), i = 2, . . . , m, we obtain: ω(x) (m + 1)l(p 1 )/2. Putting all this together we finally get:

m(x, y) = l (p 1 ) mopt(x) m + 1 + ω(x) m + 1 q.e.d.

Structure in differential approximation classes

What has been discussed in the previous sections makes clear that the entire theory of approximation, that tries to characterize and to classify problems with respect to their approximability hardness, can be redone in the differential paradigm. There exist problems having several differential-approximability levels and inapproximability bounds. What follows further confirms this claim. It will be shown that the approximation paradigm we deal with, allows to devise its proper tools and to use them in order to design an entire structure for the approximability classes involved.

Differential NPO-completeness

Obviously, the strict reduction of [START_REF] Orponen | On approximation preserving reductions: complete problems and robust measures[END_REF] (see also [START_REF] Ausiello | Completeness in differential approximation classes[END_REF]), can be identically defined in the framework of the differential approximation; for clarity, we denote this derivation of the strict reduction by D-reduction. Two NPO problems will be called D-equivalent if there exist D-reductions from any of them to the other one. Theorem 3.1 in [START_REF] Orponen | On approximation preserving reductions: complete problems and robust measures[END_REF] (where the differential approximation ratio is mentioned as possible way of estimating the performance of an algorithm), based upon an extension of Cook's proof ( [START_REF] Cook | The complexity of theorem-proving procedures[END_REF]) of SAT NP-completeness to optimization problems, works also when the differential ratio is dealt instead the standard one. Furthermore, solution triv, as defined in [START_REF] Orponen | On approximation preserving reductions: complete problems and robust measures[END_REF] is indeed a worst solution for min wsat. On the other hand, the following proposition holds. Sketch of proof. With any clause ℓ 1 ∨. . .∨ℓ t of an instance ϕ of max wsat, we associate in the instance ϕ ′ of min wsat the clause l1 ∨ . . . ∨ lt . Then, if an assignment y satisfies the instance ϕ, the complement y ′ of y satisfies ϕ ′ , and vice-versa. So, m(ϕ, y) = n i=1 w(x i )m(ϕ ′ , y ′ ), for any y ′ . Thus, δ(ϕ, y) = δ(ϕ ′ , y ′ ). The reduction from min wsat to wsat is completely analogous.

In a completely analogous way, as in Proposition 2, it can be proved that min 0-1 integer programming and max 0-1 integer programming are also D-equivalent. Putting all the above together the following holds Theorem 7. max wsat, min wsat, min 0-1 integer programming and max 0-1 integer programming are NPO-complete under D-reducibility.

The class 0-DAPX

Informally, class 0-DAPX is the class of NPO problems for which the differential ratio of any polynomial algorithm is equal to 0. In other words, for any such algorithm, there exists an instance on which it will compute its worst solution. Such situation draws the worst case for the differential approximability of a problem. Class 0-DAPX is defined in [START_REF] Ausiello | Completeness in differential approximation classes[END_REF] by means of a reduction, called G-reduction. It can be seen as a particular kind of the GAP-reduction ( [START_REF] Arora | Hardness of approximation[END_REF][START_REF] Ausiello | Complexity and approximation[END_REF][START_REF] Vazirani | Approximation algorithms[END_REF]). Definition 3. A problem Π is said to be G-reducible to a problem Π ′ , if there exists a polynomial reduction that transforms any δ-differential approximation algorithm for Π ′ , δ > 0 into an optimal algorithm for Π.

Let Π be an NP-complete decision problem and Π ′ an NPO problem. The underlying idea for Π G Π ′ in definition 3 is, starting from an instance of Π, to construct instances for Π ′ that have only two distinct feasible values and to prove that any differential for Π ′ , δ > 0, could distinguish between positive instances and negative instances for Π. Note finally that the G-reduction generalizes both the D-reduction of Section 4.1 and the strict reduction of [START_REF] Orponen | On approximation preserving reductions: complete problems and robust measures[END_REF].

Sketch of proof.

Given an instance ϕ of sat with n variables x 1 , . . . , x n and m clauses C 1 , . . . , C m , construct a graph G, instance of min independent dominating set associating with any positive literal x i a vertex u i and with any negative literal xi a vertex v i . For i = 1, . . . , n, draw edges (u i , v i ). For any clause C j , add in G a vertex w j and an edge between w j and any vertex corresponding to a literal contained in C j . Finally, add edges in G in order to obtain a complete graph on w 1 , . . . , w m An independent set of G contains at most n + 1 vertices. An independent dominating set containing the vertices corresponding to true literals of a non satisfiable assignment and one vertex corresponding to a clause not satisfied by this assignment, is a worst solution of G of size n + 1. If ϕ is satisfiable then opt(G) = n. If ϕ is not satisfiable then opt(G) = n + 1. So, any independent dominating set of G has cardinality either n, or n + 1.

By analogous reductions, restricted versions of optimum weighted satisfiability problems are proved 0-DAPX in [START_REF] Th | Complexité et approximation polynomiale[END_REF].

the following relationship between NPO and 0-DAPX holds. If, instead D, a stronger reducibility is considered, for instance, by allowing f and/or g to be multivalued in the strict reduction, then, under this type of reducibility, it can be proved that NPO-complete = 0-DAPX ([3]).

DAPX-and Poly-DAPX-completeness

In this section we address the problem of completeness in the classes DAPX and Poly-DAPX.

For this purpose, we first introduce a differential approximation schemata preserving reducibility, originally presented in [START_REF] Ausiello | Completeness in differential approximation classes[END_REF], called DPTAS-reducibility.

Definition 5. Given two NPO problems Π and Π ′ , Π DPTAS-reduces to Π ′ if there exist a (possibly) multi-valued function f = (f 1 , f 2 , . . . , f h ), where h is bounded by a polynomial in the input-length, and two functions g and c, computable in polynomial time, such that:

• for any x ∈ I Π , for any ǫ ∈ (0, 1) ∩ Q, f (x, ǫ) ⊆ I Π ′ ;

• for any x ∈ I Π , for any ǫ ∈ (0, 1) ∩ Q, for any x ′ ∈ f (x, ǫ), for any y ∈ sol Π ′ (x ′ ), g(x, y, ǫ) ∈ sol Π (x);

• c : (0, 1) ∩ Q → (0, 1) ∩ Q;

• for any x ∈ I Π , for any ǫ ∈ (0, 1) ∩ Q, for any y ∈ ∪ h i=1 sol Π ′ (f i (x, ǫ)), ∃j h such that δ Π ′ (f j (x, ǫ), y) 1c(ǫ) implies δ Π (x, g(x, y, ǫ)) 1ǫ.

It can be easily shown that given two NPO problems Π and Π ′ , if Π DPTAS Π ′ and Π ′ ∈ DAPX, then Π ∈ DAPX.

DAPX-completeness

If one restricts her/himself to problems with polynomially computable worst solutions, then things are rather simple. Indeed, given such a problem Π ∈ DAPX, it is affine equivalent to a problem Π ′ defined on the same set of instances and with the same set of solutions but, for any solution y of an instance x of Π, the measure for solution y with respect to Π ′ is defined as m Π ′ (x, y) = m Π (x, y)ω(x). Affine equivalence of Π and Π ′ ensures that Π ′ ∈ DAPX; furthermore, ω Π ′ (x) = 0. Since, for the latter problem, standard and differential approximation ratios coincide, it follows that Π ′ ∈ APX. max independent set is APX-complete under PTASreducibility ( [START_REF] Crescenzi | On approximation scheme preserving reducibility and its applications[END_REF]), a particular kind of the AP-reducibility [START_REF] Ausiello | Complexity and approximation[END_REF][START_REF] Crescenzi | Structure in approximation classes[END_REF][START_REF] Crescenzi | On approximation scheme preserving reducibility and its applications[END_REF]. So, Π ′ PTAS-reduces to max independent set. Putting together affine equivalence between Π and Π ′ , PTAS-reducibility between Π ′ and max independent set, and taking into account that composition of these two reductions is an instantiation of DPTAS-reduction, we conclude the DAPX-completeness of max independent set.

However, things become much more complicated, if one takes into account problems with nonpolynomially computable worst solutions. In this case, one needs more sophisticated techniques and arguments. We informally describe here the basic ideas and the proof-schema in [START_REF] Ausiello | Completeness in differential approximation classes[END_REF]. It is first shown that any DAPX Π is reducible to max wsat-B by a reduction transforming a polynomial time approximations schema for max wsat-B into a polynomial time differentialapproximation schema for Π. For simplicity, denote this reduction by S-D. Next, a particular APX-complete problem Π ′ is considered, say max independent set-B. max wsat-B, that is in APX, is PTAS-reducible to max independent set-B. max independent set-B is both in APX and in DAPX and, moreover, standard and differential approximation ratios coincide for it; this coincidence draws a trivial reduction called ID-reduction. It trivially transforms a differential polynomial time approximation schema into a standard polynomial time approximation schema. The composition of the three reductions specified (i.e., the S-D-reduction from Π to max wsat-B, the PTAS-reduction from max wsat-B to max independent set-B and the ID-reduction) is a DPTAS-reduction transforming a polynomial time differential-approximation schema for max independent set-B into a polynomial time differential-approximation schema for Π, i.e., max independent set-B is DAPX-complete under DPTAS-reducibility.

Also, by standard reductions that turn out to be DPTAS-reductions also, the following can be proved.

Poly-DAPX-completeness

Let us notice first that, for reasons very cleverly explained in [START_REF] Khanna | On syntactic versus computational views of approximability[END_REF] for the standard paradigm, use of restrictive reductions as the E-reducibility introduced there, where the functions f and g do not on any parameter ǫ seems very unlikely to be able to handle Poly-APX-completeness. For this reason, in [START_REF] Khanna | On syntactic versus computational views of approximability[END_REF], only Poly-APX-completeness for polynomially bounded problems is handled. As it is shown in [START_REF] Bazgan | Completeness in standard and differential approximation classes: Poly-(D)APX-and (D)PTAS-completeness[END_REF], in order to handle the whole Poly-APX-completeness, less restrictive reducibilities are needed. The same observation can be done also for Poly-DAPXcompleteness and any translation of E-reducibility to the differential paradigm.

Fortunately, the scope of the DPTAS-reducibility is large enough to allow not only apprehension of DAPX-completeness but also of Poly-DAPX-completeness. Recall that a maximization problem Π ∈ NPO is canonically hard for Poly-APX ( [START_REF] Khanna | On syntactic versus computational views of approximability[END_REF]), if and only if there exist a polynomially computable transformation T from 3sat to Π, two constants n 0 and c and a function F , hard for Poly8 , such that, given an instance x of 3sat on n n 0 variables and a number N n c , the instance x ′ = T (x, N ) belongs to I Π and verifies the three following properties:

(i) if x is satisfiable, then opt(x ′ ) = N ; (ii) if x is not satisfiable, then opt(x ′ ) = N/F (N ); (iii) given a solution y ∈ sol Π (x ′
) such that m(x ′ , y) > N/F (N ), one can polynomially determine a truth assignment satisfying x.

Based upon DPTAS-reducibility and the notion of canonical hardness, the following is proved in [START_REF] Bazgan | Completeness in standard and differential approximation classes: Poly-(D)APX-and (D)PTAS-completeness[END_REF].

Theorem 12 immediately implies that, on the one hand, the closure of DPTAS under DFTreducibility is the whole NPO and, on the other hand that any NP-hard problem in NPO-DPB∩ DPTAS is DPTAS-complete under DFT-reducibility.

Consider now min planar vertex cover, max planar independent set and bin packing. They are all NP-hard and in NPO-DPB. Furthermore, they are all in DPTAS (for the first two problems, this is derived by the inclusion of max planar independent set in PTAS proved in [START_REF] Baker | Approximation algorithms for NP-complete problems on planar graphs[END_REF]; for the third one, revisit Section 3.1.2). So, the following theorem holds and concludes this section.

Theorem 13. ( [START_REF] Bazgan | Completeness in standard and differential approximation classes: Poly-(D)APX-and (D)PTAS-completeness[END_REF]) max planar independent set, min planar vertex cover and bin packing are DPTAS-complete under DFT-reducibility.

Finally, dealing with the scope of DFT-reducibility, it is proved in [START_REF] Bazgan | Completeness in standard and differential approximation classes: Poly-(D)APX-and (D)PTAS-completeness[END_REF] that if there exist NPOintermediate problems under Turing-reducibility, then there exit problems that are DPTASintermediate, under DFT-reducibility.

Discussion and final remarks

As we have already claimed in the beginning of Section 4, the entire theory of approximation can be reformulated in the differential paradigm. This paradigm has the diversity of the standard one, it has a non-empty scientific content and, to our opinion, it represents in some sense a kind of revival for the domain of the polynomial approximation.

Since the work in [START_REF] Demange | On an approximation measure founded on the links between optimization and polynomial approximation theory[END_REF], a great number of paradigmatic combinatorial optimization problems has been studied in the framework of the differential approximation. For instance, knapsack has been sudied in [START_REF] Demange | On an approximation measure founded on the links between optimization and polynomial approximation theory[END_REF] and revisited in [START_REF] Hassin | z-approximations[END_REF]. max cut, min cluster, stacker crane, min dominating set, min disjoint cycle cover, max acyclic subgraph, min feedback arc set been dealt in [START_REF] Hassin | z-approximations[END_REF]. min vertex cover and max independent set are studied in [START_REF] Demange | On an approximation measure founded on the links between optimization and polynomial approximation theory[END_REF] and in [START_REF] Hassin | z-approximations[END_REF]. min coloring is dealt in [START_REF] Demange | Approximation results for the minimum graph coloring problem[END_REF][START_REF] Demange | Differential approximation algorithms for some combinatorial optimization problems[END_REF][START_REF] Hassin | Maximizing the number of unused colors in the vertex coloring problem[END_REF][START_REF] Halldórsson | Approximating discrete collections via local improvements[END_REF][START_REF] Halldórsson | Approximating k-set cover and complementary graph coloring[END_REF][START_REF] Duh | Approximation of k-set cover by semi-local optimization[END_REF][START_REF] Bazgan | Completeness in standard and differential approximation classes: Poly-(D)APX-and (D)PTAS-completeness[END_REF], while min weighted coloring (where the input is a vertex-weighted graph and the weight of a color is the weight of the heaviest of its vertices) is studied in [START_REF] Demange | Weighted node coloring: when stable sets are expensive[END_REF] (see also [START_REF] Demange | Time slot scheduling of compatible jobs[END_REF]). min independent dominating set is dealt in [START_REF] Bazgan | Differential approximation for optimal satisfiability and related problems[END_REF]. bin packing is studied in [START_REF] Demange | Differential approximation algorithms for some combinatorial optimization problems[END_REF][START_REF] Demange | Asymptotic differential approximation ratio: definitions, motivations and application to some combinatorial problems[END_REF][START_REF] Demange | Bridging gap between standard and differential polynomial approximation: the case of bin-packing[END_REF][START_REF] Demange | Maximizing the number of unused bins[END_REF]. min set cover, under several assumptions on its worst value, is dealt in [START_REF] Demange | On an approximation measure founded on the links between optimization and polynomial approximation theory[END_REF][START_REF] Hassin | z-approximations[END_REF][START_REF] Bazgan | On the differential approximation of min set cover[END_REF], while min weighted set cover is dealt in [START_REF] Demange | Differential approximation algorithms for some combinatorial optimization problems[END_REF][START_REF] Bazgan | On the differential approximation of min set cover[END_REF]. min tsp and max tsp, as well as, several famous variants of them, min metric tsp, max metric tsp, min tspab (the most famous restrictive case of this problem is min tsp12), max tspab are studied in [START_REF] Monnot | Differential approximation results for the traveling salesman and related problems[END_REF][START_REF] Monnot | Approximation algorithms for the traveling salesman problem[END_REF][START_REF] Monnot | Differential approximation results for the traveling salesman problem with distances 1 and 2[END_REF][START_REF] Hassin | z-approximations[END_REF][START_REF] Toulouse | Approximation polynomiale: optima locaux et rapport différentiel[END_REF]. steiner tree problems under several assumptions on the form of the input-graph and on the edge-weights are dealt in [START_REF] Demange | Differential approximation results for the steiner tree problem[END_REF]. Finally, several optimum satisfiability and constraint satisfaction problems (as max sat, max e2sat, max 3sat, max e3sat, max eksat, min sat, min ksat, min eksat, min 2sat and their corresponding constraint satisfaction versions) are studied in [START_REF] Escoffier | Differential approximation of min sat, max sat and related problems[END_REF].

Dealing with structural aspects of approximation, besides the existing approximability classes (defined rather upon combinatorial arguments) two logical classes have been very notorious in the standard paradigm. These are Max-NP and Max-SNP, originally introduced in [START_REF] Papadimitriou | Optimization, approximation and complexity classes[END_REF] (see also [START_REF] Ausiello | Complexity and approximation[END_REF][START_REF] Th | Complexité et approximation polynomiale[END_REF]). Their definitions, independent from any approximation ratio consideration, make that they can identically be considered also in differential approximation. In the standard paradigm, the following strict inclusions hold: PTAS ⊂ Max-SNP ⊂ APX and MAX-NP ⊂ APX. As it is proved in [START_REF] Escoffier | Differential approximation of min sat, max sat and related problems[END_REF], max sat / ∈ DAPX, unless P = NP. This, draws an important structural difference in the landscape of approximation classes in the two paradigms, since an immediate corollary of this result is that MAX-NP ⊂ DAPX. Position of Max-SNP in the differential landscape is not known yet. It is conjectured, however, that MAX-SNP ⊂ DAPX. In any case, formal relationships of Max-SNP and Max-NP with the other differential approximability classes deserve further study.

2 .

 2 output B = argmin{|B k | : k = 0, . . . , n -1}. Let B * be the optimal solution claimed by Lemma 1. Then, B * 2 is an optimal solution for the sub-list L k * . Observe that Algorithm SA called by DA has also been executed on L k * and denote by B k * the solution so computed by DA. The solution returned in Step 2 verifies |B| |B k * |. Finally, since any bin in B * 2 contains at least two items, |L k * | = nk * 2opt(L k *

3 .

 3 output the best among the three solutions computed in Step 2. Theorem 3. ([25]) Algorithm DSCHEMA is a polynomial time differential-approximation schema for bin packing. So, bin packing ∈ DPTAS. Sketch of proof. Since ρ and ǫ do not depend on n, neither does η, computed at Step 1. Consequently, by Lemma 2, execution of EBP Step 2 can be performed in polynomial time and, if |L k * +1 |η, it provides some optimal solution for L. On the other hand, if |L k * +1 | 2(ρ -1 + ǫ)/ǫ 2 , Algorithm PTDAS achieves, by Lemma 3, differential-approximation ratio 1ǫ for any possible value of opt(L k * +1 ).

Proposition 2 .

 2 ([3]) max wsat and min wsat are D-equivalent.

Definition 4 .

 4 0-DAPX is the class of NPO problems Π ′ for which there exists an NP-complete problem Π G-reducible to Π ′ . A problem is said to 0-DAPX-hard, if any problem in 0-DAPX G-reduces to it.An obvious consequence of Definition 4 is that 0-DAPX is the class of NPO problems Π for which approximation within any differential approximation ratio δ > 0 would entail P = NP. Proposition 3. ([START_REF] Bazgan | Differential approximation for optimal satisfiability and related problems[END_REF]) min independent dominating set ∈ 0-DAPX.

Theorem 8 .

 8 ([3]) Under D-reducibility, NPO-complete = 0-DAPX-complete ⊆ 0-DAPX.

Theorem 9 .

 9 ([3, 9]) max independent set-B, min vertex cover-B, for fixed B, max k-set packing, min k-set cover, for fixed k, and min coloring are DAPX-complete under DPTAS-reducibility.

This notation is suggested in[START_REF] Demange | On an approximation measure founded on the links between optimization and polynomial approximation theory[END_REF]; another notation drawing the same measure is z-approximation suggested in[START_REF] Hassin | z-approximations[END_REF].

The case where optimal values are bounded by fixed constants.

The same holds for the condition opt(x) k induced by the hardness criterion in the standard paradigm.

A property is hereditary if whenever is true for some set, it is true for any of its subsets; it is non-trivial if it is true for infinitely many sets and false for infinitely many sets also.

It is well-known that the independence property is hereditary.

A minimum total weight partial subgraph of Kn any vertex of which has degree at most 2; this computation is polynomial, see, for example[START_REF] Cook | Combinatorial Optimization[END_REF]; in other words a 2-matching is a collection of paths and cycles, but when dealing with complete graphs a 2-matching can be considered as a collection of cycles.

The set of functions from N to N bounded by a polynomial ; a function f ∈ Poly is hard for Poly, if and only if there exist three constants k, c and n0 such that, for any n n0, f (n) kF (n c ).

is completely different when dealing with differential approximation where min tsp ∈ APX. This result draws another notorious difference between the two paradigms.

Consider an edge-weighted complete graph of order n, denoted by K n and observe that the worst min tsp-solution in K n is an optimal solution for max tsp. Consider the following algorithm (originally proposed by [START_REF] Monnot | Differential approximation results for the traveling salesman and related problems[END_REF] for max tsp) based upon a careful patching of the cycles of a minimum-weight 2-matching 7 of K n :

• if k is even (resp., odd), then set:

• output T the best among T 1 , T 2 and T 3 .

As it is proved in [START_REF] Monnot | Differential approximation results for the traveling salesman and related problems[END_REF], the set (M \ ∪ 3 i+1 R i ) ∪ 3 i+1 A i is a feasible solution for min tsp, the value of which is a lower bound for ω(K n ); furthermore:

Then, a smart analysis, leads to the following theorem (the same result has been obtained, by a different algorithm working also for negative edge-weights, in [START_REF] Hassin | z-approximations[END_REF]). Theorem 4. ( [START_REF] Monnot | Differential approximation results for the traveling salesman and related problems[END_REF]) min tsp is differentially 2/3-approximable.

Notice that min tsp, max tsp, min metric tsp and max metric tsp all affine equivalent (see [START_REF] Monnot | Approximation algorithms for the traveling salesman problem[END_REF] for the proof; for the two former of them, just replace weight d(i, j) of edge (v i , v j ) by Md(i, j), where M is some number greater than the maximum edge weight). Hence, the following theorem holds. As it is shown in [START_REF] Khanna | On syntactic versus computational views of approximability[END_REF], max independent set is canonically hard for Poly-APX. Furthermore, min vertex cover is affine equivalent to max independent set. Henceforth, use of Theorem 10, immediately derives the following result.

Theorem 11. max independent set and min vertex cover are complete for Poly-DAPX under DPTAS-reducibility.

Finally let us note that, as it is proved in [START_REF] Bazgan | Completeness in standard and differential approximation classes: Poly-(D)APX-and (D)PTAS-completeness[END_REF], max independent set is Poly-APX-complete under PTAS-reducibility.

DPTAS-completeness

Completeness in DPTAS is tackled by means of a kind of reducibility preserving membership in DFPTAS, which is called DFT-reducibility in [START_REF] Bazgan | Completeness in standard and differential approximation classes: Poly-(D)APX-and (D)PTAS-completeness[END_REF]. Definition 6. ( [START_REF] Bazgan | Completeness in standard and differential approximation classes: Poly-(D)APX-and (D)PTAS-completeness[END_REF]) Let Π and Π ′ be two NPO problems. Let Π ′ α be an oracle for Π ′ producing, for any α ∈ (0, 1] any instance x ′ of Π ′ , a feasible solution Π ′ α (x ′ ) of ′ that is an differential approximation. Π DFT-reduces to Π ′ if and only if, for any ǫ > 0, there exists an algorithm A ǫ (x, Π ′ α ) such that:

• for any instance x of Π, A ǫ returns a feasible solution which is a (1ǫ)-differential approximation;

) runs in time polynomial with both |x ′ | and 1/α, then A ǫ is polynomial with both |x| and 1/ǫ. DPTAS-reduction under DFT-reducibility can be easily derived by two intermediate lemmata.

The first one introduces some property of the seminal Turing-reducibility (see [START_REF] Ausiello | Complexity and approximation[END_REF] for formal definition). Before stating the second lemma, we need to introduce the class of diameter polynomially bounded problems that is a subclass of the radial problems seen in Section 2.2. An NPO problem Π is diameter polynomially bounded if and only if, for any x ∈ I Π , |opt(x)ω(x)| q(|x|). The class of diameter polynomially bounded NPO problems will be denoted by NPO-DPB.

The second lemma claims that, under certain conditions, a Turing-reduction (that only preserves optimality) can be transformed into an DFT-reduction. Informally, starting from a Turingreduction between two NPO problems Π and Π ′ , where Π ′ is polynomially bounded, one can devise a DFT-reduction transforming a fully polynomial time differential-approximation schema for Π ′ into a fully polynomial time differential-approximation schema for Π.