Vincent Mousseau
email: mousseau@lamsade.dauphine.fr

Luís C Dias
email: ldias@inescc.pt

José Figueira
email: figueira@fe.uc.pt

Dealing with inconsistent judgments in multiple criteria sorting models

Keywords: Multicriteria Decision Aiding, Sorting problem, Inconsistent judgment, Assignment examples, Inconsistency analysis for LP

assignment examples 2.1 Defining confidence levels . . . . . . . . .

Introduction

Many real-world decision problems can be represented by a model stating explicitly the multiple points of view from which alternatives under consideration should be evaluated, through the definition of n crit criterion functions g 1 , g 2 , . . . , g j , . . . , g n crit . Given a set A = {a 1 , a 2 , . . . , a i , . . . , a n alt } of potential alternatives evaluated on the criteria, the analyst conducting the decision aiding study may formulate the problem in different terms. B. Roy [START_REF] Roy | Multicriteria Methodology for Decision Aiding[END_REF] distinguishes among three problem statements, i.e., problem formulations (choosing, sorting and ranking) that may guide the analyst in structuring the decision problem (see also [1]). Among these problem statements, a major distinction concerns relative vs absolute judgments of alternatives. This distinction refers to the way alternatives are considered and to the type of result expected from the analysis.

In the first case, alternatives are directly compared one to each other and the results are expressed using the comparative notion of "better " vs. "worse". Choosing (selecting a subset of the best alternatives) or ranking (defining a preference order on A) are typical examples of comparative judgments. The presence (or absence) of an alternative a i in the set of the best alternatives results from the comparison of a i to the other alternatives. Similarly, the position of an alternative in the preference order depends on its comparison to the others.

In the second case, each alternative is considered independently from the others in order to determine its intrinsic value by means of comparisons to norms or references; it consists of assigning each alternative to one of the pre-defined categories C 1 , C 2 , ..., C k , ..., C ncat . The assignment of an alternative a i results from its intrinsic evaluation on all criteria with respect to the norm defining the categories. Several methods have been proposed to handle multiple criteria sorting problems (MCSP), e.g., Trichotomic Segmentation [9], N-TOMIC [8], ORCLASS [START_REF] Larichev | An approach to ordinal classification problems[END_REF], ELECTRE TRI [15], PROAFTN [2], UTADIS [START_REF] Zopounidis | Multicriteria preference disaggregation for classification problems with an application to global investing risk[END_REF] and a general class of filtering methods [12].

One of the main difficulties that an analyst must face when interacting with a decision maker (DM) in order to build a sorting model is the elicitation of various preference parameters used by the method. Even when these parameters can be interpreted, it is difficult to fix directly their values and to have a clear understanding of the implications of these values in terms of the output of the model. In order to avoid direct elicitation of the parameters, several authors have designed disaggregation procedures which allow to infer parameter's values from holistic judgments (such a disaggregation approach was first introduced in the UTA method [START_REF] Jacquet-Lagrèze | Assessing a set of additive utility functions for multicriteria decision making: the UTA method[END_REF]). Such procedures have been defined for MCSP e.g., [START_REF] Zopounidis | Multicriteria preference disaggregation for classification problems with an application to global investing risk[END_REF] for UTADIS and [11] for ELECTRE TRI.

The holistic judgments required to infer sorting models are called assignment examples and correspond to alternatives (actual or fictitious) for which the DM can express a desired assignment, e.g., "a i should be assigned to C 3 " (a i → C 3 ), or "a i should be assigned to

C 1 or C 2 " (a i → [C 1 , C 2 ],
i.e., imprecise assignment examples can be considered). In some sorting methods (namely UTADIS and ELECTRE TRI when only the weights of criteria are inferred) such assignment examples define linear constraints on the model parameters.

In order to minimize the differences between the assignments made by the method and the assignments made by the DM, a mathematical program infers the values for these parameters that best restore the DM's judgments. Such a methodology requires from the DM much less cognitive effort than a direct elicitation of parameters (the elicitation of parameters is done indirectly using holistic information given by the DM) and provides a factual justification for the values assigned to the parameters.

Inference procedures are usually not designed as a problem to be solved only once, but rather several times in an interactive learning process, where the DM continuously revises the information they provide as they learn from the results of the inference programs (see [3]). At each iteration, the DM has the opportunity to revise assignment examples. This interactive process stops when the DM is satisfied with the values of the parameters and when the results of the model (i.e., assignment of alternatives to categories) match their view of the decision problem.

During this interactive process, the DM might provide inconsistent judgments, i.e., a set of assignment examples that cannot be satisfied simultaneously by the sorting model. Such inconsistencies can arise for several reasons (cognitive limitations, evolution of preferences during the process, ...). In such a situation, it is not always easy for the DM to identify the reasons for inconsistencies. Moreover, there usually exists more than one way to restore consistency. Hence, the DM need support in inconsistency analysis.

Consider a problem in which a DM has interactively specified assignment examples inducing linear inequalities on the preference parameters. This is namely the case with UTADIS [START_REF] Zopounidis | Multicriteria preference disaggregation for classification problems with an application to global investing risk[END_REF] and ELECTRE TRI [3] when only the weights of criteria are inferred. Let x 1 , x 2 , . . . , x j , . . . , x n denote the n parameters of the considered sorting model. The assignment examples define a polyhedron of possible values for the parameters, T = {x ∈ R n : n j=1 α ij x j ≥ β i , i = 1, . . . , m}; when an inconsistent set of assignment examples is provided by the DM, this polyhedron is empty. There exist various ways by which the set of assignment examples can be modified so that the polyhedron T becomes non empty.

The problem is then to identify all the "minimal" subsets (minimal in the sense of the inclusion) that resolve inconsistency, i.e., subsets among which the DM must choose in order to make his/her information consistent. In [10] two algorithms are proposed to identify all the minimal subsets S q , q = 1, . . . , Q to be deleted (sorted by cardinality) that resolve inconsistency and whose cardinality is lower than (or equal to) maxcount (maxcount is an input to the algorithms that states the maximum number of solutions to be computed).

In this paper we propose alternative ways to resolve inconsistencies stemming from a set of assignment examples; namely, instead of deleting assignment examples, we consider relaxing them, i.e., enlarging the interval of the possible assignments for an alternative. Moreover, we consider that the DM may provide confidence levels associated with the assignment examples; such information can be exploited to find a way to solve inconsistency that best them.

The paper is organized as follows. Section 1 defines inconsistency relaxation and shows that the algorithms proposed by [10] still apply when considering constraints relaxation rather than constraints deletion. The section 2 considers the case where the DM is able to provide confidence levels associated to the assignment examples. We provide two ways to account for such information in order to rank the solutions according to the confidence levels provided by the DM. Section 3 provides an illustrative example within the context of the ELECTRE TRI.

Inconsistency resolution via constraints relaxation

Resolving the inconsistencies can be performed by deleting a subset of constraints. Let us denote I = {1, 2, ..., m} the set of indices of the constraints and T ∅ = {x ∈ R n : n j=1 α ij x j ≥ β i , ∀i ∈ I} the initial empty polyhedron, i.e., with all the constraints. Let S ⊆ I denote a subset of indices of constraints. We will say that S resolves the inconsistency if and only if the polyhedron

T S = { n j=1 α ij x j ≥ β i , ∀i ∈ I \ S} is not empty.
In [10] two algorithms are proposed to compute alternative ways to restore consistency by constraints deletion. We consider here the case where consistency can be solved by relaxing constraints rather than deleting them. Considering an infeasible system of linear inequalities (that can correspond to assignment examples), relaxing constraints rather than deleting them (in order to restore feasibility) has already been studied in the general case by (e.g., [13] and [7]). The relaxations considered by these authors are continuous and deal with the right-hand-side of the constraints only. In our case, we will define the relaxations differently:

• the relaxations will be performed by changing the technical coefficients of the constraints rather than the right-hand-side; • a discrete set of relaxations will be considered which have a meaning in the sorting model, namely increasing the interval of categories to which an alternative can be assigned.

Suppose the DM has specified a set of assignment examples, i.e., a subset of alternatives A * ⊆ A such that each a i ∈ A * is associated with max(a i ) (min(a i ), respectively) the index of the maximum (minimum, respectively) category to which a i should be assigned according to their holistic preferences (a i → [min(a i ), max(a i )], a i ∈ A * ). From the DM's perspective, max(a i ) represents the statement "a i should be assigned at most to category C max(a i ) " and, min(a i ) express that "a i should be assigned at least to category C min(a i ) ". For each a i ∈ A * , min(a i ) and max(a i ) induce (when considering UTADIS and ELECTRE TRI) two linear constraints. Note that trivial constraints such as min(a i ) = C min and/or max(a i ) = C max do not need to be taken into account.

Let us consider the assignment example a

i → [min(a i ), max(a i )], a i ∈ A * . A relaxation of this assignment example consists of assigning a i to a wider interval [C k , C k ′ ] such that k ≤ min(a i ) or k ′ ≥ max(a i )
, with at least one strict inequality. Let us consider the system of inequalities containing the constraints corresponding to all the possible relaxations of the assignment example a i → [min(a i ), max(a i )] (it also contains the constraints corresponding to the original assignment example). It should be noticed that all the constraints corresponding to a relaxation of one of the two initial constraints are redundant. Consider S the set of all indices of constraints induced from a set of assignment examples corresponding to a relaxation of the initial assignment examples. Therefore we can note that S contains many redundancies.

If we apply the algorithms proposed by [10] (i.e., inconsistency resolution via constraints deletion) to the set S, the solutions correspond to constraints relaxation and/or deletion. It follows from the preceding remark that it is possible to use the algorithm proposed by [10] to solve inconsistencies by relaxation (rather than deletion) of assignment examples. Hence, in the rest of the paper, we will talk in terms of constraints deletion, knowing that it embraces the case of constraints relaxation.

Attributing confidence levels to assignment examples

In the course of the interactive process that aims at inferring the parameters of a sorting model, the DM provides assignment examples. For each assignment example, DMs might be more or less confident in their statements. Let us suppose that they are able to express confidence judgments during the interactive process. Such confidence judgments can be taken into account when an inconsistency arises. More precisely, algorithms that identify alternative ways for solving inconsistencies may use such information. Intuitively, these algorithms should provide solutions in an order such that the least confident constraints are relaxed/deleted with a higher priority than solutions relaxing more confident statements.

Defining confidence levels

Let us consider a confidence scale on the assignment examples Ψ = {ψ 0 , ψ 1 , . . . , ψ p , . . . , ψ τ }, where ψ 0 (ψ τ , respectively) corresponding to the minimum (maximum, respectively) confidence level, and ≺ denote an order on Ψ (ψ 0 ≺ ψ 1 ≺ . . . ≺ ψ p ≺ . . . ≺ ψ τ ). The semantic of this qualitative scale is such that, when facing an inconsistency situation, an assignment example is less likely to be relaxed/deleted when its confidence level is high.

From the DM's perspective, a i → max(a i ) represents the statements "a i should be assigned at most to category C max(a i ) " and, min(a i ) express that "a i should be assigned at least to category C min(a i ) ". These two statements induce two constraints. The DM can attach a confidence level to each of the above mentioned statements. This information will be interpreted as confidence levels attached to the corresponding constraints (for example, a 1 → C 2 implies "a 1 should be assigned at least to C 2 " and "a 1 should be assigned at most to C 2 " and the DM may have different confidence levels concerning these two statements, e.g., they may say that if a 1 is not assigned to C 2 , then it is more likely to be assigned to a higher category than to a lower one). For each relaxed constraint, the attached confidence level corresponds to the confidence level of the original constraint from which it was derived (unless the DM provides specific information).

A lexicographic ranking procedure

Let us consider an inconsistent set of assignment examples provided by the DM and the set of linear constraints associated with these examples. Any relaxation of these assignment examples (see §1) will be also considered here. Following the notation introduced previously, m denotes the total number of constraints and I = {1, 2, . . . , i, . . . , m} denotes the set of indices of these constraints. The resulting polyhedron is,

T ∅ = {x ∈ R n : n j=1 α ij x j ≥ β i , ∀i ∈ I} = ∅
Let I p denote the subset of constraints whose confidence level is equal to ψ p . Hence, I 0 , I 1 , ..., I p , ..., I τ define a partition of I. Furthermore, we will denote I ≤p = p l=0 I l the set of constraints whose confidence level is lower than or equal to ψ p . Now, consider S l ⊆ I ≤l a subset of indices of constraints whose confidence level is lower than or equal to ψ l . We will say that S l resolves the inconsistency at a confidence level ψ l if and only if

T S l = {x ∈ R n : n j=1 α ij x j ≥ β i , ∀i ∈ I \ S l } = ∅.
A simple way to account for the confidence level attached to each constraint is to proceed as follows:

1. Identify (by increasing order of cardinality) all minimal subsets S 0 1 , S 0 2 , ..., S 0 q 0 that resolve the inconsistency at level ψ 0 (i.e., relaxations whose confidence level is equal to ψ 0 that make the original system of inequalities feasible).

2. Then, identify (by increasing order of cardinality) all minimal subsets S 1 1 , S 1 2 , ..., S 1 q 1 that resolve the inconsistency at level ψ 1 .

3. Proceed in the same way until finding minimal subsets S τ 1 , S τ 2 , ..., S τ qτ that resolve the inconsistency at level ψ τ or finding a total number of subsets equal to maxcount.

The program P M 0 1 identifies the smallest set of constraints S 0 1 whose confidence level is equal to

ψ 0 so that T S 0 1 = {x ∈ R n : n j=1 α ij x j ≥ β i , ∀i ∈ I \ S 0 1 } = ∅ P M 0 1              M in I ≤0 y i s.t. n j=1 α ij x j + M y i ≥ β i , ∀i ∈ I ≤0 n j=1 α ij x j ≥ β i , ∀i ∈ I \ I ≤0 x j ≥ 0, j = 1, . . . , n y i ∈ {0, 1}, i ∈ I ≤0 (1)
where, M is a positive large number; the variables y i , i ∈ I ≤0 , are the binary variables assigned to each constraint index in S whose confidence index is lower than or equal to ψ 0 . The indices of constraints for which y * i = 1 (at the optimum of P M 0 1 ) constitute the subset S 0 1 .

P M 0 2 is defined in order to compute S 0 2 . This new program is derived from P M 0 1 by adding the single constraint i∈S 0 1

y i ≤ |S 0 1 | -1.
This constraint makes it impossible to find S 0 1 (the optimal solution of P M 0 1 ) or any solution that includes this set. A third program P M 0 3 is then defined by adding the constraint i∈S 0 2 y i ≤ |S 0 2 | -1, and so on until we reach an infeasible program, meaning that there are no more solutions in I ≤0 . When all the solutions in I ≤0 are found, the algorithm starts to search for solutions in I ≤1 . The first solution S 1 1 is found by solving P M 1 1 which is derived from the previous program by replacing the constraints

n j=1 α ij x j + M y i ≥ β i , ∀i ∈ I ≤0 and n j=1 α ij x j ≥ β i , ∀i ∈ I \ I ≤0 by n j=1 α ij x j + M y i ≥ β i , ∀i ∈ I ≤1 and n j=1 α ij x j ≥ β i , ∀i ∈ I \ I ≤1 .
The algorithm continues until finding maxcount solutions (or no more solution exists).

Begin

p ← 0 count ← 0 While (p ≤ τ ) and (count ≤ maxcount) q ← 1 moresol ← true While moresol Solve P M p q If (P M p q has no solution) or (count>maxcount) Then moresol ← false Else S p q ← {i ∈ I :

y * i = 1} Add constraint i∈S p q y i ≤ |S l k | -1 to P M p q so as to define P M p q+1 q ←q+1 count ←count+1 End if End while p ←p+1

End while End

This algorithm requires to solve several 0-1 programs. Note that it is possible to design an algorithm for the same purpose using only linear programming (see the second algorithm presented in [10]).

A penalty based ranking procedure

Defining a penalty function

Another approach to our problem consists of defining a penalty function π(S) associated to each subset of constraints indices S ⊆ I, and to rank the subsets that resolve the inconsistency by decreasing penalty order: the larger π(S), the greater the insatisfaction of the DM in removing S from I. This approach generalizes the lexicographic ranking as it is possible to define the penalty function π in a way that the penalty ranking coincides with the lexicographic ranking.

Given a subset S ⊆ I, S ∩ I p denotes the subset of S corresponding to constraints indices whose confidence level is equal to ψ p , p = 0, ..., τ . Let |S ∩ I p | denote the cardinality of S whose confidence level is equal to ψ p .

In order to define the semantic of the penalty function π, we impose a few suitable conditions on π: These conditions express natural properties for a function π to define a consistent penalty function:

Condition 2.1. (non-negativity) ∀S ⊆ I, π(S) ≥ π(∅) = 0. Condition 2.2. (anonymity) ∀S, S ′ ⊆ I, if |S ∩ I p | = |S ′ ∩ I p |, ∀p = 0, ..., τ then π(S) = π(S ′ ). Condition 2.3. (confidence monotonicity) ∀S, S ′ ⊆ I such that |S ∩ I p | = |S ′ ∩ I p |, p = 1, . . . , τ, p = u, p = v, it holds: |S ′ ∩ I u | = |S ∩ I u | + 1 |S ′ ∩ I v | = |S ∩ I v | -1 u < v    ⇒ π(S) > π(S ′ )
• Condition 2.1 (non-negativity) states that π has a lower bound (arbitrarily set to 0). Although it is not necessary, it would be possible to impose also an upper bound on the penalties, for instance π(I) = 1. In such a case, the penalty function π could be understood as a "disutility" function related to a utility function u(.) = 1π(.). This would be of interest in that the questioning techniques used to elicit multi-attribute utility functions [5] from the DM can be used in this context.

• Condition 2.2 (anonymity) states that the penalty of a set S only depends on the number of constraints of each confidence level contained in S regardless of the constraints "label".

• Condition 2.3 (confidence monotonicity) states that considering a solution S, if the confidence level of one constraint in S decreases, then π(S) should also decrease.

• Condition 2.4 (cardinality monotonicity) states that if a solution S contains less (or equal) constraints than another solution S ′ , for each confidence level, the penalty should be lower (or equal) for S than for S ′ .

Among the possible penalty functions, one of the simplest can be defined considering that each constraint in S of a given confidence level ψ p contributes to increase π(S) by an amount ∆ p (the values ∆ p are to be defined by the DM):

π(S) = τ p=0 ∆ p |S ∩ I p | (2)
Considering condition 2.3, the amounts for ∆ 0 , ..., ∆ τ should be such that u < v ⇒ ∆ u < ∆ v . This simple model can be generalized by considering that the penalty does not increase linearly with respect to the number of constraints:

π(S) = τ p=0 π p (|S ∩ I p |) (3)
where π p (n) is a function (to be defined by the DM) denoting the penalty of removing n constraints of confidence level ψ p (given the assumed conditions, π p must be an increasing function).

More sophisticated non-additive models may be envisaged, namely those taking into account preference dependencies among different confidence levels.

Ranking solutions according to the penalty function

Given a penalty function π, it is necessary to define an algorithm to rank by increasing penalty the subsets of I that, if removed, yield a consistent system. In order to design an algorithm to identify the maxcount subsets of constraints that solve inconsistency and rank them according to the penalty function π, we will adapt the algorithms presented by [10] which rank by increasing cardinality all minimal subsets that resolve inconsistency : S 1 , S 2 , . . . , S q , . . .

(|S q | ≤ |S q+1 |).
The algorithms presented in [10] provide the set of the solutions ordered by cardinality without any consideration about confidence levels. In our case, we want to provide the set of (at most) maxcount solutions ordered by increasing penalty. It should be noticed that the smallest cardinality solutions might not correspond to those of the smallest penalty. Therefore, we can proceed by computing the solutions by increasing cardinality and stop when we are sure that the solutions of a higher cardinality have a greater penalty than the ones we already obtained.

Let S x,p denote an arbitrary set of x constraints, all of confidence levels equal to ψ p .

Proposition 2.1. ∀S ⊆ I, S ′ ⊆ I : |S| ≥ |S ′ |, it holds π(S) ≥ π(S |S ′ |,0 ) i.e.
, the penalty of any solution after the q-th is not lower than the penalty that would be awarded to the q-th solution if all the constraints indexed by S q were of the lowest confidence.

Proof. From repeatedly using Condition 2.3, π(S) ≥ π(S |S|,0 ). From Condition 2.4, since |S| ≥ |S ′ |, it holds that π(S |S|,0 ) ≥ π(S |S ′ |,0 ).

In the following algorithm, TOP-N denotes a list of solutions of at most maxcount elements, ordered by increasing penalty, and S tail denotes the last solution (i.e., the solution with the highest penalty) of list TOP-N. At the end of the algorithm, TOP-N contains the maxcount first solutions ordered by increasing penalty.

Begin

q ← 0 TOP-N ← empty list S tail ← first solution repeat S q ← q th solution provided by the algorithm in [10] If (q ≤ maxcount) or (π(S q ) < π(S tail ))

Then S q enters TOP-N End If Until S q = ∅ or (q ≥ maxcount and π(S tail ) ≤ π(S |Sq|,0 )) End

In this algorithm, when S q enters TOP-N it does so respecting the penalty ranking. If the list is full (when it contains maxcount elements), this implies removing the highest penalty element (S tail ), and the variable S tail will be updated. Proposition 2.1 allows us to define the stopping condition π(S tail ) ≤ π(S |Sq|,0 )).

Illustrative example

Let us consider a situation in which a set of 40 alternatives has to be assigned to 5 categories using the ELECTRE TRI pessimistic method. Each alternative is evaluated on the basis of a set of 7 criteria (see Appendix A). The limits of categories are known but the criteria importance coefficients are to be defined (see Appendix B). Suppose the DM provides assignment examples with associated level of confidence on a scale (absolutely confident ≻ quite confident ≻ not so confident), where

a i → [C k , C k ′ ]
means that alternative a i must be assigned to a category between C k and C k ′ , (k ≤ k ′ ):

• a 1 → C 5 , not so confident • a 18 → C 4 , quite confident • a 23 → [C 2 , C 3 ], not so confident • a 24 → [C 2 , C 3 ], quite confident • a 26 → C 5 , quite confident • a 30 → C 1 , not so confident • a 31 → C 5 , not so confident • a 35 → [C 1 , C 2 ], absolutely confident • a 36 → C 4 , quite confident • a 38 → C 4 , not so confident • a 39 → C 3 , not so confident
From these assignment examples, it is possible to define relaxations as defined in Section 1. In this example, we will suppose that the relaxations have the same confidence level than their corresponding assignment examples. For instance, the relaxations corresponding to the assignment example

a 1 → C 5 are a 1 → [C 4 , C 5 ], a 1 → [C 3 , C 5 ] and a 1 → [C 2 , C 5 ] (note that the relaxation a 1 → [C 1 , C 5 ]
amounts at removing the assignment example a 1 → C 5 ).

These assignment examples and their relaxations generate a set of 41 constraints on the criteria weights w j , j = 1, ..., 7 and cutting level λ which are presented in Appendix C. The first 17 constraints correspond to the original assignment examples and the remaining ones correspond to the relaxations. The linear system associated with the assignment examples is infeasible, which means that the information provided by the DM is inconsistent, i.e. there is no way to represent this information in the ELECTRE TRI sorting model.

Considering this infeasible linear system, there exist 11 minimal subsets of constraints that resolve the inconsistency, where I = {1, 2, ..., 41}. These 11 subsets (ordered by cardinality) are listed below. Let us remark that due to the limited size of this example, we have computed all the solutions. Such a way of proceeding is time consuming when dealing with real world problems of large size .

• S 1 = {5, 8, 9, 10, 11, 25, 28, 29} To solve the inconsistency, the DM should choose one among these 11 alternative solutions. In order to be presented to the DM, these solutions should be formulated in terms of relaxation of the assignment examples. For instance, S 1 corresponds to (the formulation of the other solutions are provided in Appendix D):

           relax a 23 → [C 2 , C 3 ] to a 23 → [C 2 , C 4 ] relax a 26 → C 5 to a 26 → [C 3 , C 5 ] relax a 30 → C 1 to a 30 → [C 1 , C 4 ] relax a 31 → C 5 to a 31 → [C 4 , C 5 ] relax a 35 → [C 1 , C 2 ] to a 35 → [C 1 , C 3 ] (4)
We can observe that some of these relaxations correspond to the deletion of one constraint from

I (relax a 23 → [C 2 , C 3 ] to a 23 → [C 2 , C 4
], constraint 5), while others require the deletion of several constraints from I (relax a 26 → C 5 to a 26 → [C 3 , C 5 ], constraints 8 and 25). Moreover, S 1 suggests to relax assignment examples whose associated confidence levels are "not so confident" (a 23 , a 30 and a 31 ), "quite confident" (a 26 ) or "absolutely confident" (a 35 ).

When interacting with the DM to solve an inconsistency, it is not reasonable to propose him/her a large number of alternative solutions. It is convenient to propose a limited number of solutions that might be interesting for him/her. In our case, we wish to propose approximately 5 solutions to the DM (maxcount=5).

If we consider the confidence judgments, the lexicographic ranking algorithm presented in §2.2 computes the solutions, considering first the solutions that removes constraints which are "not so confident" (i.e., I ≤0 ), then the solutions removing constraints that are "not so confident" or "quite confident" (i.e., I ≤1 ) and finally the remaining ones. In each group, the solutions are computed by increasing order of cardinality. In our example, no solution exists removing only "not so confident" constraints; the first five solutions computed only involve the deletion of constraints that are "not so confident" or "quite confident": If the DM provides a penalty function π(.), then the penalty based procedure presented in §2.3 may also be used. For instance, let us consider a penalty function as in (2), with ∆ 0 = 1, ∆ 1 = 2 and ∆ 2 = 3. The five best solutions are: Using either of these rankings of solutions, the DM is to chose among the "most promising" solutions to solve inconsistency. Hence, this largely reduces the cognitive effort of the DM to resolve inconsistency.

• S 3 = {1,
• S 5 = {1,

Conclusion

In this paper, we considered the problem of supporting the DM in the resolution of inconsistent judgments expressed in the form of assignment examples in multiple criteria sorting model. We have proposed the concept of relaxation of an assignment example, which is helpful in this context. To resolve the inconsistency, it is useful to obtain from the DM confidence statements associated with the assignment examples. We have proposed procedures that account for this information to assist the DM in finding the most relevant ways to restore consistency.

An illustrative example has been provided to show how the proposed procedures can be used within the context of the ELECTRE TRI sorting method. However, our procedures are general and apply to any sorting method for which assignment examples generate linear constraints on the preference-related parameters.

An interesting extension of this work consists in considering the possibility of associating different confidence levels to the original assignment examples constraints and their corresponding relaxation. This extension amounts at considering that the various relaxations of an assignment example are not judged as equivalent as regards their confidence levels.

Appendices

Appendix A: Evaluation matrix

g 1 (a i ) g 2 (a i ) g 3 (a i ) g 4 (a i ) g 5 (a i ) g 6 (a i )

Condition 2 . 4 .

 24 (cardinality monotonicity) ∀S, S ′ ⊆ I, if ∀p = 0, ..., τ, |S ∩ I p | ≥ |S ′ ∩ I p | then π(S) ≥ π(S ′ ).

  8, 9, 10, 14, 25, 28, 29, 31}, π(S 5 ) = 10 • S 1 = {5, 8, 9, 10, 11, 25, 28, 29}, π(S 1 ) = 11 • S 3 = {1, 5, 8, 9, 10, 14, 17, 28, 29}, π(S 3 ) = 11 • S 4 = {1, 5, 8, 9, 10, 14, 25, 28, 29}, π(S 4 ) = 11 • S 7 = {5, 7, 9, 10, 11, 13, 17, 28, 29, 30}, π(S 7 ) = 11

  • S 2 = {5, 8, 9, 10, 11, 17, 28, 29} • S 3 = {1, 5, 8, 9, 10, 14, 17, 28, 29} • S 4 = {1, 5, 8, 9, 10, 14, 25, 28, 29} • S 5 = {1, 8, 9, 10, 14, 25, 28, 29, 31} • S 6 = {1, 8, 9, 10, 11, 25, 28, 29, 31} • S 7 = {5, 7, 9, 10, 11, 13, 17, 28, 29, 30} • S 8 = {1, 8, 9, 10, 12, 14, 16, 25, 28, 31, 38} • S 9 = {5, 8, 9, 10, 11, 12, 14, 16, 25, 28, 31, 38} • S 10 = {3, 5, 7, 9, 11, 13, 15, 17, 23, 24, 28, 29, 30, 41} • S 11 = {1, 2, 4, 6, 8, 10, 12, 14, 16, 18,19, 20, 21, 22, 25, 26, 27, 31, 32, 33, 36, 37, 38, 39, 40}

  5, 8, 9, 10, 14, 17, 28, 29} • S 4 = {1, 5, 8, 9, 10, 14, 25, 28, 29} • S 5 = {1, 8, 9, 10, 14, 25, 28, 29, 31} • S 7 = {5, 7, 9, 10, 11, 13, 17, 28, 29, 30} • S 8 = {1, 8, 9, 10, 12, 14, 16, 25, 28, 31, 38}

  g 7 (a i )Appendix D: Solutions of the inconsistency problemIn the example provided in section 3, there exist 11 solutions to solve the inconsistency, i.e., * • S 1 = {5, 8, 9, 10, 11, 25, 28, 29} • S 2 = {5, 8, 9, 10, 11, 17, 28, 29} • S 3 = {1, 5, 8, 9, 10, 14, 17, 28, 29} • S 4 = {1, 5, 8, 9, 10, 14, 25, 28, 29} • S 5 = {1, 8, 9, 10, 14, 25, 28, 29, 31} • S 6 = {1, 8, 9, 10, 11, 25, 28, 29, 31} • S 7 = {5, 7, 9, 10, 11, 13, 17, 28, 29, 30} • S 8 = {1, 8, 9, 10, 12, 14, 16, 25, 28, 31, 38} • S 9 = {5, 8, 9, 10, 11, 12, 14, 16, 25, 28, 31, 38} • S 10 = {3, 5, 7, 9, 11, 13, 15, 17, 23, 24, 28, 29, 30, 41} • S 11 = {1, 2, 4, 6, 8, 10, 12, 14, 16, 18, 19, 20, 21, 22, 25, 26, 27, 31, 32, 33, 36, 37, 38, 39, 40} These solutions correspond to changes in the original assignment examples. These modifications of the original assignment examples are presented bellow: S 1 original assignment relaxed assignment a 23 [C 2 , C 3 ] [C 2 , C 4 ]

	S 9 original assignment relaxed assignment
	a 1 a	C 5 [C 2 , C 3 ]		[C 4 , C 5 ] [C 2 , C 4 ]
	a a	[C 2 , C 3 ] C 5		[C 2 , C 4 ] [C 3 , C 5 ]
	a a	C 5 C 1		[C 3 , C 5 ] [C 1 , C 3 ]
	a a	a 0 C 1 C 5	35.8	67 [C 1 , C 4 ] 19.7 [C 3 , C 5 ]	0	0	5
	a a	a 1 C 5 [C 1 , C 2 ]	16.4	14.5 [C 4 , C 5 ] 59.8 [C 1 , C 3 ]	7.5	5.2	5
	a a	a 2 C 4 C 4	35.8	24 [C 3 , C 4 ] 64.9 [C 3 , C 4 ]	2.1	4.5	5
	a	a 3 C 4	20.6	61.7 [C 2 , C 4 ] 75.7	3.6	8	5
	a 4 S 5 original assignment relaxed assignment 11.5 17.1 57.1 a C3 [C 2 , C 3 ]	4.2	3.7	5
	a 5 a 6 a 7 C 5 C 5 S original assignment relaxed assignment 22.4 25.1 49.8 23.9 34.5 48.9 29.9 44 57.8 a 1 [C 4 , C 5 ] a [C 3 , C 5 ] a 8 8.7 5.4 27.4 a C 1 [C 1 , C 4 ] a C 4 [C 4 , C 5 ] a 9 25.7 29.7 46.8 a C 5 [C 3 , C 5 ] a [C 2 , C 3 ] [C 2 , C 5 ] a 10 21.2 24.6 64.8 a C 4 [C 3 , C 4 ] a [C 2 , C 3 ] [C 2 , C 5 ] a 11 18.3 31.6 69.3 a C 1 [C 1 , C 5 ] a 12 20.7 19.3 19.7 S 6 original assignment relaxed assignment a [C 1 , C 2 ] [C 1 , C 3 ] a 13 9.9 3.5 53.1 a 14 10.4 9.3 80.9 a 15 17.7 19.8 52.8 a 1 C 5 a C 4 [C 4 , C 5 ] [C 4 , C 5 ] a C 5 a C 4 [C 4 , C 5 ] [C 3 , C 5 ] a C 1 [C 1 , C 4 ] a C 3 [C 3 , C 5 ] a 16 14.8 15.9 27.9 16 14.7 53.5 a C 5 [C 3 , C 5 ] a [C 1 , C 2 ] [C 1 , C 3 ] S original assignment relaxed assignment a 17 a 18 11.7 10 42.1 12.2 5 2.5 1.7 4.5 4.6 3.6 2.8 2.2 8.5 1.4 7.9 5.4 6.8 a 19 11 4.2 60.8 6.2 a 20 15.5 8.5 56.2 5.5 a 21 13.2 9.1 74.1 6.4 a 22 9.1 4.1 44.8 3.3 a 23 12.9 1.9 65 14 a 24 5.9 -27.7 77.4 16.6 a 25 16.9 12.4 60.1 5.6 a 26 16.7 13.1 73.5 11.9 a 27 14.6 9.7 59.5 6.7 a 26 C 5 a 1 C 5 [C 1 , C 5 ] [C 3 , C 5 ] a 30 C 1 S 7 original assignment relaxed assignment a C 4 [C 1 , C 4 ] [C 1 , C 4 ] a 31 C 5 [C 4 , C 5 ] a 35 [C 1 , C 2 ] [C 1 , C 3 ] S 2 original assignment relaxed assignment a 23 [C 2 , C 3 ] [C 2 , C 4 ] a 26 C 5 [C 4 , C 5 ] a 30 C 1 [C 1 , C 4 ] a [C 2 , C 3 ] a [C 2 , C 3 ] [C 1 , C 3 ] [C 2 , C 4 ] a [C 2 , C 3 ] a [C 2 , C 3 ] [C 1 , C 3 ] [C 2 , C 4 ] a C 1 a C 5 [C 1 , C 5 ] [C 1 , C 5 ] a C 5 a C 5 [C 1 , C 5 ] [C 4 , C 5 ] a [C 1 , C 2 ] a C 4 [C 1 , C 4 ] [C 1 , C 3 ] a C 4 a C 4 [C 1 , C 4 ] [C 4 , C 5 ] a C 3 [C 3 , C 4 ] a C 3	7.9 8 2.5 4.5 3.7 8 3 4 5.3 4.1 6.1 1.8 3.8 4.3 4.8 1.8 5 10.4 7.5 12.7 5.6 4.1 5.6	5 5 5 5 4 4 4 4 4 4 4 4 4 5 4 4 2 3 4 3 3 2 2
	a 28 a 29 24.4 5.1 a 30 29.5 a 31 7.3 C 5 [C 1 , C 2 ] S 8 original assignment relaxed assignment 4.9 28.9 22.3 32.8 8.6 41.8 -64.5 67.5 30.1 2.5 3.3 5.2 a 31 [C 4 , C 5 ] a 35 [C 1 , C 3 ] a 39 C 3 a 1 C 5 [C 4 , C 5 ] [C 3 , C 4 ] a C 5 [C 3 , C 5 ] a 32 23.7 31.9 63.6 12.1 a 33 18.9 13.5 74.5 12 a 34 13.9 3.3 78.7 14.7 a 35 -13.3 -31.1 63 21.2 a 36 6.2 -3.2 46.1 4.8 a 37 4.8 -3.3 71.1 8.6 a 38 0.1 -9.6 42.5 12.9 a 39 13.6 9.1 76 17.1 a 39 C 3 [C 3 , C 4 ] a 38 C 4 [C 3 , C 4 ] a 31 C 5 [C 4 , C 5 ] a C 1 [C 1 , C 3 ] S 3 original assignment relaxed assignment a 1 C 5 a C 5 [C 3 , C 5 ] [C 4 , C 5 ] a 23 [C 2 , C 3 ] a C 4 [C 3 , C 4 ] [C 2 , C 4 ] a 26 C 5 a C 4 [C 2 , C 4 ] [C 4 , C 5 ] a 30 C 1 [C 1 , C 4 ] a C 3 [C 2 , C 3 ]	46 5 6.4 8.7 10.2 8.4 10.1 29.1 10.5 11.6 12.4 10.3	2 3 2 3 3 3 2 2 2 1 1 2

[C 1 , C 3 ]

Acknowledgements: This work has benefited from the luso-french grant n o 500B4 (ICCTI / Ambassade de France au Portugal) and program PESSOA 2004 (GRICES/EGIDE). The third author was also supported by the grant SFRH/BDP/6800/2001.


Bruno Escoffier
email: escoffier@lamsade.dauphine.fr

Vangelis Th

Paschos
email: paschos@lamsade.dauphine.fr

Differential approximation of MIN SAT, MAX SAT and related problems

We present differential approximation results (both positive and negative) for optimal satisfiability, optimal constraint satisfaction, and some of the most popular restrictive versions of them. As an important corollary, we exhibit an interesting structural difference between the landscapes of approximability classes in standard and differential paradigms.

Introduction and preliminaries

In this paper we deal with the approximation of some of the most famous and classical problems in the domain of the polynomial time approximation theory, the  and   as well as the  and   and some of their restricted versions, namely  and  k and k and  and  k and k. We study their approximability using the so-called differential approximation ratio which, informally, for an instance x of a combinatorial optimization problem Π, measures the relative position of the value of an approximated solution in the interval between the worst-value of x, i.e., the value of a worst feasible solution of x, and optimal-value of x, i.e., the value of a best solution of x.

Given a set of clauses (i.e., disjunctions) C 1 , . . . , C m on n variables x 1 , . . . , x n ,   (resp.,  ) consists of determining a truth assignment to the variables that maximizes (minimizes) the number of clauses satisfied. On the other hand, given a set of cubes (i.e., conjunctions) C 1 , . . . , C m on n variables x 1 , . . . , x n ,   (resp.,  ) consists of determining a truth assignment to the variables that maximizes (minimizes) the number of conjunctions satisfied. For an integer k 2,  k,  k,  k,  k (resp.,  k,  k,  k,  k) are the versions of  ,  ,  ,   where each clause or conjunction has size at most (resp., exactly) k; we denote by   k ,   k ,   k and   k , the problems variants where clauses or cubes have size at least k. Finally, let us quote two particular weighted satisfiability versions, namely,   and  . In the former, given a set of clauses C 1 , . . . , C m on n variables x 1 , . . . , x n , with non-negative integer weights w(x) on any variable x, we wish to compute a truth assignment to the variables that both satisfies all the clauses and maximizes the sum of the weights of the variables set to 1. We consider that the assignment setting all the variables to 0 (even if it does not satisfy all the clauses) is feasible and represents the worst-value solution for the problem. The latter problem is similar to the former one, up to the fact that we wish to minimize the sum of the weights of the variables set to 1 and that feasible is now considered the assignment setting all the variables to 1.

A problem Π in NPO is a quadruple (I Π , Sol Π , m Π , opt(Π)) where:

• I Π is the set of instances (and can be recognized in polynomial time);

• given x ∈ I Π , Sol Π (x) is the set of feasible solutions of x; the size of a feasible solution of x is polynomial in the size |x| of the instance; moreover, one can determine in polynomial time if a solution is feasible or not;

• given x ∈ I Π and y ∈ Sol Π (x), m Π (x, y) denotes the value of the solution y of the instance x; m Π is called the objective function, and is computable in polynomial time; we suppose here that m Π (x, y) ∈ N;

• opt(Π) ∈ {min, max}.

Given an instance x of an optimization problem Π and a feasible solution y ∈ Sol Π (x), we denote by opt Π (x) the value of an optimal solution of x, and by ω Π (x) the value of a worst solution of x. The standard approximation ratio of y is defined as r Π (x, y) = m Π (x, y)/ opt Π (x), while the differential approximation ratio of y is defined as

δ Π (x, y) = |m Π (x, y) -ω Π (x)|/| opt Π (x) -ω Π (x)|.
For a function f of |x|, an algorithm is a standard f -approximation algorithm (resp., differential fapproximation algorithm) for a problem Π if, for any instance x of Π, it returns a solution y such that

r(x, y) f (|x|), if opt(Π) = min, or r(x, y) f (|x|), if opt(Π) = max (resp., δ(x, y) f (|x|)).
With respect to the best approximation ratios known for them, NPO problems can be classified into approximability classes. The most notorious among them are the following: APX or DAPX: the class of problems for which there exists a polynomial algorithm achieving standard or differential approximation ratio f (|x|) where function f is constant (it does not depend on any parameter of the instance);

PTAS or DPTAS: the class of problems admitting a polynomial time approximation schema; such a schema is a family of polynomial algorithms A ε , ε ∈]0, 1], any of them guaranteeing approximation ratio 1 -ε (under the differential approximation paradigm and under the standard one in the case where opt(Π) = max), or 1 + ε (under the standard approximation paradigm in the case where opt(Π) = min); FPTAS and DFPTAS: the class of problems admitting a fully polynomial time approximation schema; such a schema is a polynomial time approximation schema (A ε ) ε∈]0,1] , where the complexity of any A ε is polynomial in both the size of the instance and in 1/ε.

We now define a kind of reduction, called affine reduction and denoted by AF, which, as we will see, is very natural in the differential approximation paradigm.

Definition 1. Let Π and Π ′ be two NPO problems. Then, Π AF-reduces to Π ′ (Π ≤ AF Π ′ ), if there exist two functions f and g such that:

1. for any

x ∈ I Π , f (x) ∈ I Π ; 2. for any y ∈ Sol Π ′ (x), g(x, y) ∈ Sol Π (x); moreover, Sol Π (x) = g(x, Sol Π ′ (f (x))); 3. for any x ∈ I Π , there exist K ∈ R and k ∈ R ⋆ (k > 0 if opt(Π) = opt(Π ′ ), k < 0, otherwise) such that, for any y ∈ Sol Π ′ (f (x)), m Π ′ (f (x), y) = km Π (x, g(x, y)) + K.
If Π ≤ AF Π ′ and Π ′ ≤ AF Π, then Π and Π ′ are called affine equivalent. This equivalence will be denoted by

Π ≡ AF Π ′ .
It is easy to see that differential approximation ratio is stable under affine reduction. Formally, if, for Π, Π ′ ∈ NPO, R = (f, g) is an AF-reduction from Π to Π ′ , then for any x ∈ I Π and for any y ∈ Sol Π ′ (f (x)), δ Π (x, g(x, y)) = δ Π ′ (f (x), y). Indeed, by Condition 2 of Definition 1, worst and optimal solutions in x and f (x) coincide. Since the value of any feasible solution of Π ′ is an affine transformation of the same solution seen as a solution of Π, the differential ratios for y and g(x, y) coincide also. Hence, the following holds.

Proposition 1. If Π ≡ AF Π ′ , then, for any constant r, any r-differential approximation algorithm for one of them is an r-differential approximation algorithm for the other one.

Optimization satisfiability problems as   and   are of great interest from both theoretical and practical points of view. On the one hand, the satisfiability problem () is the first complete problem for NP and  ,   have generalizations or restrictions that are the first problems proved complete for numerous approximation classes under various approximability preserving reductions ( [START_REF] Ausiello | Complexity and approximation[END_REF][START_REF] Vazirani | Approximation algorithms[END_REF]). For instance,  3 is APX-complete under the AP-reduction and Max-SNP-complete under the Lreduction ( [START_REF] Papadimitriou | Optimization, approximation and complexity classes[END_REF]),   and   are NPO-complete under the AP-reduction ([8]), etc. In general, many optimal satisfiability problems have for the polynomial approximation theory the same status as  for NP-completeness theory. On the other hand, many problems in mathematical logic and in artificial intelligence can be expressed in terms of versions of ; constraints satisfaction is one such version. Also problems in database integrity constraints, query optimization, or in knowledge bases can be seen as optimization satisfiability problems. Finally, some approaches to inductive inference can be modelled as M S problems ( [START_REF] Hooker | Resolution vs. cutting plane solution of inference problems: some computational experience[END_REF][START_REF] Kamath | Computational experience with an interior point algorithm on the satisfiability problem[END_REF]). The interested reader can be referred to [START_REF] Battiti | Algorithms and heuristics for max-sat[END_REF] for a survey on standard approximability of optimization satisfiability problems.

Let us note that differential approximability of the problems dealt here, has already been studied in [START_REF] Bazgan | Differential approximation for optimal satisfiability and related problems[END_REF]. There, among other results, it was shown that   and  , as well as   and   are equivalent for the differential approximation, that all these problems are not solvable by polynomial time differential approximation schemata, unless P = NP, and, finally, that   cannot be approximately solved within differential approximation ratio 1/m 1-ǫ , for any ǫ > 0 (where m is the number of the clauses in its instance), unless NP = co-RP. Finally, let us mention here that both   and   belong to 0-DAPX, the class of the problems for which no algorithm can guarantee differential approximation ratio strictly greater than 0, unless P = NP ([16]). This class has been also introduced in [START_REF] Bazgan | Differential approximation for optimal satisfiability and related problems[END_REF] In this paper, we further study differential approximability of  ,  ,   and  , and give approximation results and inapproximability bounds for several versions of these problems. A summary of the main results obtained is presented in Table 1. As one can see from the second column of the first line of this table,   is not approximable within a constant approximation ratio, unless P = NP. This result is very interesting since it indicates that Max-NP ([17]) is not included in DAPX. This is an important difference with the standard approximability classes landscape where Max-NP ⊂ APX. Another assessment with respect to our results is that the gap between lower and upper approximation bounds for the problems dealt is still large. However, this paper undertakes a systematic study of satisfiability problems in the differential paradigm, it extends the results of [START_REF] Bazgan | Differential approximation for optimal satisfiability and related problems[END_REF] and shows that none of the most classical satisfiability problems is in 0-DAPX. This approximability class has been introduced in [START_REF] Bazgan | Differential approximation for optimal satisfiability and related problems[END_REF] and represents the worst possible configuration for differential approximation since it includes the problems for which no polynomial time approximation algorithm can guarantee differential ratio greater than 0. Inclusion of the problems dealt here in 0-DAPX or not, was a major question we handled since [START_REF] Bazgan | Differential approximation for optimal satisfiability and related problems[END_REF].

Affine reductions between optimal satisfiability problems

Let us first note that there does not exist general technique in order to transfert approximation results from differential (resp., standard) paradigm to standard (resp., differential) one, except for the case of maximization problems and for transferts between differential and standard paradigms. Proposition 2 just below deals with this last case.

Proposition 2. If a maximization problem Π can be solved within differential approximation ratio δ, then it can be solved within standard approximation ratio δ, also.

Proof. Consider any differential polynomial time approximation algorithm A guaranteeing differentialapproximation ratio δ for any instance x of a maximization problem Π. Denote by A(x), a solution computed by A when running on x. Then,

m(x, A(x)) -ω(x) opt(x) -ω(x) δ =⇒ m(x, A(x)) δ opt(x) + (1 -δ)ω(x) δ 1 ω(x) 0 =⇒ m(x, A(x)) opt(x) δ
and the claim of the proposition is proved.

Corollary 1. Any standard inapproximability bound for a maximization problem Π is also a differential inapproximability bound for Π.

We give in this section some affine reductions and equivalencies between the problems dealt in the paper. These results will allow us to focus ourselves only in the study of  ,   and their restrictions without studying explicitly  and  . We first recall a result already proved in [START_REF] Bazgan | Differential approximation for optimal satisfiability and related problems[END_REF].

Proposition 3. ([6]

)   ≡ AF   and   ≡ AF  .

The following proposition shows that one can affinely pass from  k to  (k + 1). This, allows us to transfert inapproximability bounds from  3 to  k, for any k 4.

Proposition 4.  k ≤ AF  (k + 1).

Proof. Consider an instance ϕ of  k on n variables x 1 , . . . , x n and m clauses C 1 , . . . , C m . Consider also a new variable y and build formula ϕ ′ , instance of  (k + 1) as follows: for any clause

C i = (ℓ i 1 , . . . , ℓ i k ) of ϕ, where, for j = 1, . . . , k, ℓ i j is a literal associated with x i j , ϕ ′ contains two new clauses (ℓ i 1 , . . . , ℓ i k , y) and (ℓ i 1 , . . . , ℓ i k , ȳ).
Hence, ϕ ′ is the conjunction of 2m clauses of size k + 1 on n + 1 variables. Assume any truth assignment T on the variables of ϕ and denote by (T, 1) (resp., (T, 0)) the extension of T on ϕ ′ by setting y = 1 (resp., y = 0). Then, it is easy to see that

m(ϕ ′ , (T, 1)) = m(ϕ ′ , (T, 0)) = m + m(ϕ, T ).
In other words, reduction just described, associating to any assignment T ′ of ϕ ′ its restriction T on variables x 1 , . . . , x n as assignment for ϕ, is affine and the proof of the proposition is complete.

We now show that, for k fixed, problems k and k are affine equivalent.

Proposition 5. For any fixed k,  k,  k,  k,  k,  k,  k,  k and  k are all affine equivalent.

Proof. We first prove affine equivalence between  k and  k. Given n variables x 1 , . . . , x n , denote by C k the set of clauses of size k and by C k the set of clauses of size at most k on the set {x 1 , . . . , x n }.

Let us remark that any truth assignment verifies the same number v k of clauses on C k and the same number v k of clauses on C k . Note also that, since k is assumed fixed, sets C k and C k are of polynomial size.

Let ϕ be an instance of  k on variable-set {x 1 , . . . , x n } and on a set

C = {C 1 , . . . , C m } of m clauses. Consider instance ϕ ′ on the clause-set C ′ = C k \ C.
Then, for any truth assignment T on {x 1 , . . . , x n }: m(ϕ, S) + m(ϕ ′ , S) = v k ; in other words, reduction just described is an affine reduction from  k to  k. Considering ϕ as instance of  k this time, the above describe an affine reduction from  k to  k.

Furthermore, if C is an instance of  k, then we can see the clause-set C k \ C as an instance of  k and the same arguments conclude an affine reduction from the former to the latter problem.

We now prove equivalence between versions of  and the corresponding versions of . Given a clause C = (ℓ i 1 ∨ . . . ∨ ℓ i k ) on k literals, we build the cube (conjunction) D = ( li 1 ∧ . . . ∧ li k ). Any truth assignment T on ℓ i j verifies C, if and only if it does not verify D, i.e., m(C, T ) = m -m(D, T ). This specifies an affine reduction between  k and  k,  k and  k,  k and  k and between  k and  k.

We finally show equivalence between  k and  k. We first notice that the latter problem being a sub-problem of the former one, direction  k ≤ AF  k is immediate. On the other hand, as in Proposition 4, given an instance of  k, one can construct, for any clause of size at most k, a set of clauses of size exactly k, in such a way that this reduction is affine.

Combination of equivalencies shown above completes the proof of the proposition. It is shown in [START_REF] Håstad | Some optimal inapproximability results[END_REF], respectively (see also [START_REF] Ausiello | Complexity and approximation[END_REF]), that  3 is inapproximable within standard approximation ratio (7/8) + ǫ, for any ǫ > 0, and  2 is inapproximable within standard approximation ratio (21/22) + ǫ, for any ǫ > 0 (in what follows for such results we will use, for simplicity, expression "within better than"). Discussion above, together with these bounds leads to the following result. Proposition 6.  2,  2,  2,  2,  2,  2,  2 and  2 are inapproximable within differential approximation ratio better than 21/22. Furthermore, for any k 3,  k,  k,  k and  k,  k,  k,  k and  k, are inapproximable within differential approximation ratio better than 7/8.

Proof.

Concerning  2 and associates, Corollary 1 extends the result of [START_REF] Håstad | Some optimal inapproximability results[END_REF] to the differential paradigm. Then, Proposition 5 suffices to conclude the proof.

For  k and associates, Corollary 1 extends the result of [START_REF] Karloff | A 7/8-approximation for max 3sat?[END_REF] to the differential paradigm, for  3 and Proposition 5 transferts it to  3. Then, Proposition 4 extends it for any k 4. Finally, Proposition 5 suffices to conclude the proof.

Since the satisfiability problems stated in Proposition 6 are particular cases either of  , or of  , or of  , or, finally, of  , application of Proposition 6 and of Proposition 3 concludes the following corollary.

Corollary 2.  ,  ,   and   are inapproximable within differential approximation 7/8.

Results of Corollary 2 are not the best ones. In Section 4, we strengthen the one for  . On the other hand, as it is proved in [START_REF] Bazgan | Differential approximation for optimal satisfiability and related problems[END_REF],   is inapproximable within differential ratio better than m ǫ-1 , for any ǫ > 0. Proposition 5 has to be used with some precautions in order to yield positive or negative approximation results. Indeed, if one of the problem stated in it is approximable within constant differential approximation ratio (i.e., within ratio that does not depend on an instance parameter), then this ratio is naturally transferred to all the other problems. A contrario, one can see in the proof of Proposition 5 that in many cases the number of the clauses for the derived instance can be much larger that the one for the initial instance. In such cases, if we deal with ratios functions of m the form of these ratios is certainly preserved but not their value. For instance, assume that some problem Π among the ones stated Proposition 5 is approximable within ratio f (|ϕ|), where |ϕ| denotes the number of clauses, or cubes, in ϕ, and f decreases with |ϕ|. Assume also that there exists another problem Π ′ (among the ones stated in Proposition 5) such that Π ′ ≤ AF Π and, furthermore, that this affine reduction transforms a formula ϕ ′ of Π ′ into a formula ϕ for Π. Then, it transforms an approximation ratio f (|ϕ|) for the latter into an approximation ratio f (|ϕ ′ |) for the former but, if the values |ϕ| and |ϕ ′ | are very different the one from the other, then the values of the corresponding ratios do so.

In fact, one can easily observe that affine reductions of Proposition 5 perform the following differential ratio transformations:

• reduction from  k to  k transforms ratios f (m, n) into f ((2n) k -m, n); • reduction from  k to  k transforms ratios f (m, n) into f ((2n + 1) k -m, n);
• reductions between  and  are invariant for approximation ratios;

• reduction from  k to  k transforms ratios f (m, n) into f (2 k-1 m, n + k -1).
In other words, dealing with common approximability of the problems stated in Proposition 5, the following remarks hold:

• if one of these problems is in DAPX, then all the other ones are so; Finally, reduction of Proposition 4 transforms ratios f (m, n) into f (2m, n + 1).

Positive results

Maximum satisfiability

Consider an instance ϕ of an optimal satisfiability problem, defined on n variables x 1 , . . . , x n and m clauses C 1 , . . . , C m ; consider also algorithm RSAT assigning at any variable value 1 with probability 1/2 and, obviously, value 0 with probability 1/2.Then, denoting by Sol(ϕ), the set of the 2 n possible truth assignments for ϕ, and by E(RSAT(ϕ)) the expectation of a solution computed by RSAT when running on ϕ, the following holds:

E(RSAT(ϕ)) = T ∈Sol(ϕ) m(ϕ, T )/2 n .
Algorithm RSAT can be derandomized by the following technique denoted by DSAT. For i = 1, . . . , n:

• compute E ′ i = E(m(ϕ, T )|x i = 1) and E ′′ i = E(m(ϕ, T )|x i = 0)
, where T is a random assignment and the values of the i -1 first variables have already been fixed in iterations 1, . . . i -1;

• set x i = 1, if E ′ i E ′′ i ; otherwise, set x i = 0. Lemma 1. m(ϕ, DSAT(ϕ)) E(RSAT(ϕ)). Proof. It is easy to see that E(RSAT(ϕ)) = (E ′ 1 /2) + (E ′′ 1 /2); hence max{E ′ 1 , E ′′ 1 } E(RSAT(ϕ)). Furthermore, at any of the n steps of DSAT, max{E ′ i , E ′′ i } = (E ′ i+1 /2) + (E ′′ i+1 /2) max{E ′ i+1 , E ′′ i+1 }. We so have E(RSAT(ϕ)) max{E ′ 1 , E ′′ 1 } max{E ′ n , E ′′ n } = DSAT(ϕ)
, that concludes the proof of the lemma.

Note finally, that DSAT is polynomial since, for any i = 1, . . . , n, computation of E ′ i and E ′′ i is performed in polynomial time. Indeed, for any such computation it suffices to determine with what probability any clause of ϕ is satisfied and to sum these probabilities over all the clauses of ϕ.

We are ready now to state and prove positive differential approximation results for the problems dealt here.

Proposition 7. Algorithm DSAT achieves for  k differential approximation ratio 2 k /(opt(ϕ) + 2 k ). This ratio is bounded below by 2 k /(m + 2 k ).

Proof. Note first that we can assume that opt(ϕ) > ω(ϕ) (otherwise,  k would be polynomial on ϕ). Then,

ω(ϕ) < E(RSAT(ϕ)) m(ϕ, DSAT(ϕ)) (1)
From ( 1) and given that feasible values of  k are integer, we get:

m(ϕ, DSAT(ϕ)) -ω(ϕ) 1 (2)
Since clauses in ϕ are of size k, the expectation that any of them is satisfied equals

1 -2 -k . Hence, m(ϕ, DSAT(ϕ)) E(RSAT(ϕ)) = m 1 - 1 2 k opt(ϕ) 1 - 1 2 k (3)
Using ( 2) and (3), we get:

δ(ϕ, DSAT(ϕ)) max 1 opt(ϕ) -ω(ϕ) , opt(ϕ) 1 -1 2 k -ω(ϕ) opt(ϕ) -ω(ϕ) (4)
The first term in (4) is increasing with ω(ϕ), while the second one is decreasing. Equality holds when ω(ϕ) = (opt(ϕ)(1 -2 -k )) -1. In this case, (4) gives

δ(ϕ, DSAT(ϕ)) 2 k opt(ϕ) + 2 k 2 k m + 2 k (5)
Last inequality in (5) holding thanks to the fact that opt(ϕ) m, qed. Notice that the ratio claimed by Proposition 7 increases with k. This is quite natural since for k > log m,  k is polynomial. Indeed, using (3) with such a k, we get m(ϕ, DSAT(ϕ)) opt(ϕ) -(opt(ϕ)/m) > opt(ϕ) -1, i.e., m(ϕ, DSAT(ϕ)) = m, since the feasible values of  k are integer.

We now propose a reduction transferring approximation results for   problems from standard to differential paradigm. It will be used in order to achieve differential approximation results for  ,  3 and  2.

Proposition 8. If a maximum satisfiability problem is approximable on an instance ϕ, within standard approximation ratio ρ, then it is approximable in ϕ within differential approximation ratio ρ/((1 -ρ)ω(ϕ) + 1).

Proof. Fix any maximum satisfiability problem Π, sharing the ones dealt until now, and assume that there exists a polynomial time algorithm achieving standard approximation ratio ρ for Π. Consider an instance ϕ of Π, run both A and DSAT on ϕ and retain assignment T satisfying the maximum number of clauses between A(ϕ) and DSAT(ϕ). Obviously, m(ϕ, T ) ρ opt(ϕ). Hence, the differential approximation ratio of T is δ(ϕ, T ) m(ϕ, T ) -ω(ϕ)

m(ϕ,T ) ρ -ω(ϕ) (6)
Since, as we have seen in the proof of Proposition 7, m(ϕ, T ) ω(ϕ) + 1, (6) becomes δ(ϕ, T ) 1

ω(ϕ)+1 ρ -ω(ϕ) = ρ (1 -ρ)ω(ϕ) + 1 (7)
The proof of the proposition is now complete.

From the result of Proposition 8, we can deduce several corollaries by specifying values for ω(ϕ) and ρ. The main such corollaries are stated in the propositions that follow. Before stating and proving them, let us remark that, in the case of  k

E(RSAT(ϕ)) m 1 - 1 2 k (8)
Then ( 1) and ( 8) yield:

ω(ϕ) m 1 - 1 2 k (9)
Proposition 9.   is approximable within differential approximation ratio 4.34/(m + 4.34).

Proof. We can assume ω(ϕ) m -1, otherwise (ω(ϕ) = m) all feasible solutions of ϕ have the same value. Since 1 -ρ 0, the differential ratio of ( 7) decreases with ω(I). So, it suffices to substitute m -1 for ω(ϕ), to use the fact that   is approximable within standard ratio 1/1.2987 ( [START_REF] Asano | A theoretical framework of hybrid approaches to max sat[END_REF]), and the proof of the proposition is complete. Proposition 10.  2 is approximable within differential approximation ratio 17.9/(m + 19.3), and  3 within 4.57/(m + 5.73).

Proof. For  2, remark first that, using (3), the expectation of the solution computed by the random algorithm RSAT is, using [START_REF] Engebretsen | Approximate Constraint Satisfaction[END_REF], less than, or equal to, 3m/4. Consequently, ω(ϕ) 3m/4. Next, the fact that   is approximable within standard ratio 1/1.0741 ( [START_REF] Feige | Approximating the value of two prover proof systems, with applications to max 2sat and max dicut[END_REF]) suffices to conclude the proof.

For  3, ω(ϕ) 7m/8 and ρ = 1/1.249 ( [START_REF] Trevisan | Gadgets, approximation, and linear programming[END_REF]).

Minimum satisfiability

We finish this section by studying   and some of its versions. Before stating our results, we note that algorithm RSAT can be derandomized in an exactly symmetric way, in order to provide a solution for  k with value smaller than expectation's value.

Proposition 11. If a minimum satisfiability problem is approximable on an instance ϕ, within standard approximation ratio ρ, then it is approximable in ϕ within differential approximation ratio

ρ (ρ -1) 1 -1 2 k m + ρ Proof.
As in the proof of Proposition 7, since we deal with a minimization problem, (1) becomes:

opt(ϕ) m(ϕ, DSAT(ϕ)) E(RSAT(ϕ)) < ω(ϕ) (10)
Consequently, (2) becomes: m(ϕ, DSAT(ϕ)) -ω(ϕ) 1 (11)

Bounds for MAX E3SAT

We first prove a GAP-reduction analogous to the one of Proposition 13 from any problem Π ∈ NP to  3. Note that this is the first time that a GAP-reduction is used in the differential approximation paradigm.

Proposition 14. Given a problem Π ∈ NP and a real δ > 0, there exists a polynomial transformation f from any instance I of Π into an instance of  3 such that:

• if I is a yes-instance of Π, then opt(f (I)) -ω(f (I)) (1 -2δ)m/4; • if I is a no-instance of Π, then opt(f (I)) -ω(f (I)) δm/4
Proof. We first prove that the reduction of Proposition 13 can be translated into differential paradigm also. Consider an instance I ′ = g(I) of  32 and a feasible solution x = (x 1 , x 2 , . . . , x n ) for I (we will use the same notation for both variables and their assignment) verifying k among the m equations of I ′ . Then, vector x = (1 -x 1 , . . . , 1 -x n ), verifies the m -k equations not verified by x. In other words, opt(I) + ω(I) = m; hence, function g claimed by Proposition 13 is such that:

• if I is a yes-instance of Π, then opt(I ′ ) -ω(I ′ ) (1 -2δ)m; • if I is a no-instance of Π, then opt(I ′ ) -ω(I ′ ) δm.
We are ready now to continue the proof of the proposition. Consider an instance I of  32 on n variables x i , i = 1, . . . , n and m equations of type

x i + x j + x k = β in Z/2Z, i.e.
, where variables and second members equal 0, or 1. In the same spirit as in [START_REF] Håstad | Some optimal inapproximability results[END_REF], we transform I into an instance ϕ = h(I) of  3 in the following way:

• for any equation x i + x j + x k = 0, we add in h(I) the following four clauses:

(x i ∨ x j ∨ x k ), (x i ∨ xj ∨ x k ), (x i ∨ x j ∨ xk ) and (x i ∨ xj ∨ xk );
• for any equation x i + x j + x k = 1, we add in h(I) the following four clauses:

(x i ∨ x j ∨ x k ), (x i ∨ xj ∨ x k ), (x i ∨ x j ∨ xk ) and (x i ∨ xj ∨ xk ).
It can immediately be seen that h(I) has n variables and 4m (distinct) clauses. Given a solution y for  3 on h(I), we construct a solution y ′ for I by setting x i = 1 if x i = 1 in h(I) also; otherwise, we set x i = 0.

For instance, consider equation x i + x j + x k = 0 in I. It is verified if either 0 or 2 of the variables are equal to 1. The several satisfaction possibilities for the clauses derived in h(I) for this equation are the following:

• if zero, or two variables are set to 1 (true), then all the four clauses are satisfied;

• if one, or three variables are set to 1, then 3 clauses are satisfied.

As a consequence, iterating this argument for any clause set built from an equation, we conclude that solution y for  3 on h(I) verifies m(h(I), y) = 3m+m(I, y ′ ). Since transformation between y ′ and y is bijective, we get ω(h(I)) = 3m + ω(I) and opt(h(I)) = 3m + opt(I). In other words, the reduction just described is an affine reduction from  32 to  3.

It suffices now to remark that the composition f = h • g verifies the statement of the proposition and its proof is concluded.

Proposition 14 has a very interesting corollary, expressed in the Proposition 15 just below, that exhibits another point of dissymmetry between standard and differential paradigms.

Proposition 15. Unless P = NP, no polynomial algorithm can compute, on an instance ϕ of  3 a value that is a constant approximation of the quantity opt(ϕ) -ω(ϕ).

In view of Proposition 15, what is different between standard and differential paradigms with respect to the GAP-reduction is that in the former such a reduction immediately concludes the impossibility for a problem (assume that it is a maximization one) to be approximable within some ratio, by showing the impossibility for the optimal value to be approximated within this ratio. For that, it suffices that one reads the value of the solution returned by the approximation algorithm. In the latter paradigm such a conclusion is not always immediate. In fact, a reasoning similar to the one of the standard approximation is possible when computation of the worst solution can be done in polynomial time (this is, for instance, the case of maximum independent set and of many other NP-hard problems). In this case a simple reading of the value of the approximate solution is sufficient to give an approximation of opt(x) -ω(x). A contrario, when it is NP-hard to compute ω(x) (this is the case of the problems dealt here -simply think that the worst solution for   is the optimal one for   and that both of them are NP-hard -, of travelling salesman, etc.), then reading the value m(x, y) of the approximate solution does not provide us with knowledge about m(x, y) -ω(x) and, consequently no approximation of opt(x) -ω(x) can be immediately estimated. So, use of GAP-reduction for achieving inapproximability results is different from the one paradigm to the other.

However, for the case we deal with, we will take advantage of a combination of Propositions 5 and 15 in order to achieve the inapproximability bound for  3 given in Proposition 16 that follows.

Proposition 16. Unless P = NP,  3 is inapproximable within differential approximation ratio greater than 1/2.

Proof. Assume that an approximation achieves differential ratio δ > 1/2, for  3. Then, by Proposition 5, there exists an algorithm achieving the same differential ratio for  3. Denote by T 1 and T 2 , respectively, the solutions computed by these algorithms on an instance ϕ of these problems. We have:

m (ϕ, T 1 ) -ω(ϕ) δ(opt(ϕ) -ω(ϕ)) (14)
where opt(•) and ω(•) are referred to  3. By the relations between all these parameters for the two problems specified in the proof of Proposition 5, we get:

opt(ϕ) -m (ϕ, T 2 ) δ(opt(ϕ) -ω(ϕ)) (15)
Adding ( 14) and ( 15) member-by-member, we get m(ϕ, T 1 ) -m(ϕ, T 2 ) (2δ -1)(opt(ϕ) -ω(ϕ)). So, simple reading of the values of T 1 and T 2 , can provide us a constant approximation (since δ has been assumed to be a fixed constant greater than 1/2) of the quantity opt(ϕ) -ω(ϕ), impossible by Proposition 15.

Proposition 16 together with Proposition 5 conclude the following corollary.

Corollary 5. For any k 3,  k,  k,  k and  k are differentially inapproximable within ratios better than 1/2.

MAX EkSAT, k 3

In this section, we will generalize the GAP-reduction of Proposition 14 in order to further strengthen inapproximability results of Corollary 5. x j 1 + p-1 j=1

x j 2 + p-1 j=1 x j 3 = β (16)
It is easy to see that ( 16) is verified if and only if the number of variables set to 1 is either β or β + p, or, finally, β + 2p.

Consider now the set of all the possible clauses on 3(p -1) literals issued from variables x 1 i , . . . , x p-1 i , i = 1, 2, 3. Any truth assignment will satisfy all but one clause. For example, if any variable is assigned with 1, the only unsatisfied clause is the one where all variables appear negative.

What is of interest for us is to specify when the number of variables set to 1 is either β or β +p, or, β +2p. For this, denote by C k the set of clauses on 3(p -1) literals issued from variables x 1 i , . . . , x p-1 i , i = 1, 2, 3 with exactly k negative literals. Then, a truth assignment setting k variables to 1, verifies |C k | -1 clauses of C k , while any other truth assignment on the variables of C k verifies all the |C k | clauses. So, for an equation x 1 + x 2 + x 3 = β, we will add in the instance of  3(p -1) the set C k , for k ∈ {0, . . . , 3(p -1)} and k / ∈ {β, β + p, β + 2p}. Hence, if a truth assignment for these clauses has β, or β + p, or β + 2p variables set to 1, it will verify all the clauses constructed, otherwise it will verify all but one of these clauses.

In all, for any of the variables x 1 i , . . . , x p-1 i we will build one new variable and we will transform any of the m equations of I into an equation as in [START_REF] Monnot | Approximation polynomiale des problèmes NP-difficiles : optima locaux et rapport différentiel[END_REF]. Then, for any of these new equations we add in the instance of  3(p -1) the set of clauses as built just above. The instance ϕ of  3(p -1) so constructed has n(p -1) variables and, since the number of clauses issued from any equation is no more than 2 3(p-1) , ϕ will have at most m ϕ m2 3(p-1) clauses.

Given a truth assignment T on the variables of ϕ, we set x i = |{x k i : x k i = 1 in T }|. Discussion above leads to m(ϕ, T ) = m ϕ -m + m(I, S). On the other hand, it is easy to see that our reduction implies that any solution S of I is transformed into a truth assignment T on the variables of ϕ such that the relation between the values of S and T given just above is always satisfied. This relation confirms that the reduction specified is an affine one from  3p to  3(p -1).

Finally, let us remark that it is possible that formula ϕ contains many times the same clause. This, for instance, is the case if I simultaneously contains equations say

x 1 + x 2 + x 3 = β 1 and x 1 + x 2 + x 3 = β 2 , for β 1 = β 2 .
In this case, we can modify the construction described, by building the subset of

C k or k ∈ {0, . . . , 3(p -1)} and k / ∈ {β 1 , β 1 + p, β 1 + 2p, β 2 , β 2 + p, β 2 + 2p}.
This concludes the proof of the proposition.

The result of Proposition 17 together with the result of [START_REF] Håstad | Some optimal inapproximability results[END_REF] stated in the beginning of the section and Proposition 1, lead to the following corollary. Corollary 6. For any prime p,  3(p -1) is inapproximable within differential ratio greater than 1/p. Furthermore, Propositions 4 and 5 allow us to rewrite Proposition 17 as follows.

Proposition 18. For any k 3, neither  k, nor  k can be approximately solved within differential ratio greater than 1/p, where p is the largest positive prime such that 3(p -1) k.

Easy consequences of Proposition 18 are the following differential inapproximability bounds for several instantiations of maximum and minimum k-satisfiability:

•  and  3 4 and 5 are differentially inapproximable within ratio better than 1/2;

•  and  6, . . . , 11 are differentially inapproximable within ratio better than 1/3;

•  and  12, . . . , 17 are differentially inapproximable within ratio than 1/5, . . . Finally,   being harder to approximate than any  k problem, the following result holds and concludes the section.

Proposition 19.   /

∈ DAPX.

In [START_REF] Papadimitriou | Optimization, approximation and complexity classes[END_REF] is defined a logical class of NPO maximization problems called MAX-NP. A maximization problem Π ∈ NPO belongs to Max-NP if and only if there exist two finite structures (U, I) and (U, S), a quantifier-free first order formula ϕ and two constants k and ℓ such that, the optima of Π can be logically expressed as: max

S∈S

x ∈ U k : ∃y ∈ U ℓ , ϕ(I, S, x, y)

The predicate-set I draws the set of instances of Π, set S the solutions on I and ϕ the feasibility conditions for the solutions of Π. In the same article is proved that   ∈ Max-NP and that MAX-NP ⊂ APX.

It is easy to see that ( 17) can be identically used in both standard and differential paradigms. So, Proposition 19 draws an important structural difference in the landscape of approximation classes in the two paradigms, since an immediate corollary of this proposition is that MAX-NP ⊂ DAPX. We conjecture that the same holds for the other one of the celebrated logical classes of [START_REF] Papadimitriou | Optimization, approximation and complexity classes[END_REF], the class MAX-SNP, i.e., we conjecture that MAX-SNP ⊂ DAPX

MAX E2SAT

We have already seen in Proposition 6 that  2 is differentially inapproximable within ratio 21/22. In this section, we improve this result by operating an affine reduction from  22 to  2.

Indeed, consider an instance I of the former problem (on n variables and m equations) and an equation x 1 + x 2 = 0 in I. Add in ϕ (the instance of  2 under construction) clauses x1 ∨ x 2 and x 1 ∨ x2 . On the other hand, for an equation x 1 + x 2 = 1, add in ϕ clauses x 1 ∨ x 2 and x1 ∨ x2 . Performing this transformation for any equation in I, we finally build a formula ϕ of  2 on n variables and 2m clauses. Moreover, for any truth assignment T on the variables of ϕ, one gets a solution S for I such that m(ϕ, T ) = m + m(I, S), qed.

It is shown in [START_REF] Håstad | Some optimal inapproximability results[END_REF] that  22 is inapproximable within standard approximation ratio better than 11/12. By Proposition 2, this bound is transferred to the differential paradigm. Then, the affine reduction just described concludes the following result.

Proposition 20.  22 ≤ AF  2. Consequently,  2 is differentially inapproximable within ratio greater than 11/12.

Ideas for further research

We give in this concluding section a few ideas about possible ways for further improving results of the paper or for yielding new ones.

Consider a graph G(V, E) of order n and with maximum degree ∆. We construct an instance ϕ of   on n variable x 1 , . . . , x n and n cubes C 1 , . . . , C n as follows: for any vertex v i ∈ V , with neighbors v i 1 , . . . , v i δ i , we add in ϕ clause x i ∧ xi 1 ∧ . . . ∧ xi δ i . Let T be a truth assignment satisfying k cubes, say C j 1 , . . . , C j k . Then, obviously, the vertex-set V ′ = {v j 1 , . . . , v j k } is an independent set for G (of size k). Conversely, given an independent set of G of size k consisting of vertices v j 1 , . . . , v j k , the truth assignment setting variables x j 1 , . . . , x j k to 1 and any othe variable of ϕ in 0 satisfies k cubes. Observe finally that the size of the cubes built for ϕ is bounded by ∆ + 1. In all we have just exhibited an affine reduction from   -∆ (i.e.,    on graphs with maximum degree bounded by ∆) to  ∆ + 1.

On the other hand, there exists an ǫ > 0 such that, for any ∆ 3,   -∆ is not approximable within approximation ratio 1/∆ ǫ ( [START_REF] Alon | Derandomized graph products[END_REF]). Since standard and differential approximation ratios coincide for    (the worst independent set in a graph is the empty set), the result of [START_REF] Alon | Derandomized graph products[END_REF] holds immediately for differential paradigm and can be used in order to conclude that there exists an ǫ > 0 such that, for any k 4,  k is not differentially approximable within ratio greater than 1/k ǫ . This recovers the result of Proposition 19, namely, that   / ∈ DAPX.

If one wishes to improve this result, a possible issue is the following. Recall that transformation of  k to  k of Proposition 5, consists of substituting any cube of size ℓ by 2ℓ -1 clauses of size ℓ. We so can affinely (but not polynomially) reduce    to   by building an instance ϕ of the latter on n variabes and at most n2 ∆+1 clauses. But, if ∆ is bounded by log n, then this reduction is polynomial. In other words, if one obtains an inapproximability bound for   -log n (for example a bound of the type 1/ log ǫ n, for some positive ǫ), then one can extend it immediately to   improving so the bound of the paper.

•

  problems  k, k,  k  and  k are approximable within differential ratios of O(f (m)) for a function f strictly decreasing with m if and only if one of them is O(f (m)) differentially approximable for f (m) = O(m α ), for some α > 0, or f (m) = O(log m); the same holds for the quadruple  k, k,  k  and  k; • all problems are in Log-DAPX (the class of problems differentially approximable within ratios of O(1/ log |x|)) if and only if one of them is so (observe that reductions dealt transform differential ratios of O(log m) into ratios of the form O(log m) or of O(log n), and ratios of O(log n) into ratios of the same form).

Proposition 17 .

 17 For any prime p > 0,  3p ≤ AF  3(p -1). Proof. Consider a positive prime p and an instance I of  3p on n variables and m equations. Consider an equation x 1 + x 2 + x 3 = β (in Z/pZ) of I and, for any i = 1, 2, 3, p -1 new variables x 1 i , . . . , x p-1 i ∈ {0, 1}. Consider, finally, equation p-1 j=1

Table 1 :

 1 ]. Summary of the main results of the paper.

		Approximation ratios	Inapproximability bounds
	 	4.34/(m + 4.34)	/ ∈ DAPX
	 2	17.9/(m + 19.3)	11/12
	 3	4.57/(m + 5.73)	1/2
	 3	8/(m + 8)	1/2
	 k	2 k /(m + 2 k )	1/p, p the largest prime such that 3(p -1) k
	 	2/(m + 2)
	 ()k 2 k /((2 k-1 -1)m + 2 k ) 1/p, p the largest prime such that 3(p -1) k
	 2	4/(m + 4)	11/12

Considering the best among the solutions computed by DSAT and A (the ρ-standard approximation algorithm assumed for  k in the statement of the theorem), denoting it by T and using [START_REF] Feige | Approximating the value of two prover proof systems, with applications to max 2sat and max dicut[END_REF] and [START_REF] Garey | Computers and intractability. A guide to the theory of NP-completeness[END_REF], we get:

where the third term in ( 12) is due to the fact that T has a better value than the value of algorithm RSAT.

The first term in ( 12) is decreasing with ω(ϕ), while the second and third ones are increasing. We distinguish two cases depending on the relation between these terms.

If the second term is greater than the third one, i.e., if ρ opt(ϕ) m(1 -2 -k ), then equality of the first two terms of ( 12) is achieved when ω(ϕ) = 1 + ρ opt(ϕ). In this case, [START_REF] Håstad | Some optimal inapproximability results[END_REF] gives:

If, on the other hand, second term is smaller than the third one, i.e., if ρ opt(ϕ) m(1 -2 -k ), then equality of the first and the third term in ( 12) is achieved when ω(ϕ) = m(1 -2 -k ) + 1. In this case also, δ(ϕ, T ) verifies [START_REF] Hooker | Resolution vs. cutting plane solution of inference problems: some computational experience[END_REF]. The proof of the proposition is now complete.

The best standard approximation ratios known for  k and   are 2(1 -2 -k ) and 2, respectively ( [START_REF] Bertsimas | On dependent randomized rounding algorithms[END_REF]). With the ratio just mentioned for  k, the result of Proposition 11 can be simplified as indicated in the following corollary.

Proposition 12.   is approximable within differential ratio 2/(m + 2).

Proof. Use Proposition 11 with ρ = 2 ([7]).

Also, using Corollary 3 with k = 2 and k = 3, the following corollary holds and concludes the section.

Corollary 4.  2 and  3 are approximable within differential ratios 4/(m+4) and 8/(3m+8), respectively.

Inapproximability

We first recall some basics about  3p that will be used for deriving our results. In this problem, we are given a positive prime p, n variables x 1 , . . . , x n in Z/pZ, m linear equations of type α i ℓ x i ℓ + α j ℓ x j ℓ + α k ℓ x k ℓ = β ℓ and our objective is to determine an assignment on x 1 , . . . , x n , in such a way that a maximum number among the m equations is satisfied.

As it is proved in [START_REF] Håstad | Some optimal inapproximability results[END_REF] (see also [START_REF] Engebretsen | Approximate Constraint Satisfaction[END_REF] for the case where all the coefficients equal 1), for any p 2 and for any ǫ > 0,  3p cannot be approximated within standard approximation ratio (1/p) + ǫ, even if coefficients in the left-hand sides of the equations are all equal to 1. Note that, due to Corollary 1, this bound is immediately transferred to the differential paradigm.

Finally, let us quote the following GAP-reduction (see [START_REF] Arora | Hardness of approximation[END_REF] for more about this kind of reductions), proved in [START_REF] Håstad | Some optimal inapproximability results[END_REF], that will be used in order to yield our results.

Proposition 13. ([12]

) Given a problem Π ∈ NP and a real δ > 0, there exists a polynomial transformation g from any instance I of Π into an instance of  32 such that:

• if I is a yes-instance of Π (we use here classical terminology from [START_REF] Garey | Computers and intractability. A guide to the theory of NP-completeness[END_REF]), then opt(g(I)) (1 -δ)m;

Proposition 13 shows, in fact, that  32 is not approximable within standard ratio 1/2 + ǫ, for any ǫ > 0, because an algorithm achieving it would allow us to distinguish in polynomial time the yes-instances of any problem Π ∈ NP from the no-ones. Devising of such reductions is one of the most common strategies for proving inapproximability results in standard approximation.


Production de positrons à l'accélérateur d'Orsay. Détermination de la section efficace à 0°sur cibles épaisses