Structure in Approximation Classes.
The study of the approximability properties of NP-hard optimization problems has recently made great advances mainly due to the results obtained in the field of proof checking.  The last important breakthrough proves the APX-completeness of several important optimization problems and thus reconciles "two distinct views of approximation classes: syntactic and  computational" [S. Khanna et al., in  Proc. 35th IEEE Symp. on Foundations of Computer Science, IEEE Computer Society Press, Los Alamitos, CA, 1994, pp. 819--830]. In this paper we obtain new results on the structure of several computationally-defined approximation classes. In particular, after defining a new approximation preserving reducibility to be used for as many approximation classes as possible, we give the first examples of natural NPO-complete problems and the first examples of natural APX-intermediate problems.  Moreover, we state new connections between the approximability properties and the query complexity of NPO problems.
Introduction
In his pioneering paper on the approximation of combinatorial optimization problems [20],
David Johnson formally introduced the notion of approximable problem, proposed approximation
algorithms for several problems, and suggested a possible classification of optimization
problems on grounds of their approximability properties. Since then it was clear that, even
though the decision versions of most NP-hard optimization problems are many-one polynomial-time
reducible to each other, they do not share the same approximability properties. The main
reason of this fact is that many-one reductions not always preserve the objective function and,
even if this happens, they rarely preserve the quality of the solutions. It is then clear that a
stronger kind of reducibility has to be used. Indeed, an approximation preserving reduction not
only has to map instances of a problem A to instances of a problem B, but it also has to be
An extended abstract of this paper has been presented at the 1st Annual International Computing and
Combinatorics Conference.
able to come back from "good" solutions for B to "good" solutions for A. Surprisingly, the first
definition of this kind of reducibility [33] was given as long as 13 years after Johnson's paper
and, after that, at least seven different approximation preserving reducibilities appeared in the
literature (see Fig. 1). These reducibilities are identical with respect to the overall scheme but
differ essentially in the way they preserve approximability: they range from the Strict reducibility
in which the error cannot increase to the PTAS-reducibility in which there are basically no
restrictions (see also Chapter 3 of [23]).
PTAS-reducibility [14]
P-reducibility [33]L-reducibility [36] E-reducibility [26]
Strict reducibility [33]
\Phi \Phi \Phi \Phi*
\Phi \Phi \Phi \Phi*
HYH
HY
Continuous reducibility [39]
A-reducibility [33]

Figure

1. The taxonomy of approximation preserving reducibilities
By means of these reducibilities, several notions of completeness in approximation classes
have been introduced and, basically, two different approaches were followed. On the one hand,
the attention was focused on computationally defined classes of problems, such as NPO (i.e.,
the class of optimization problems whose underlying decision problem is in NP) and APX (i.e.,
the class of constant-factor approximable NPO problems): along this line of research, however,
almost all completeness results dealt either with artificial optimization problems or with problems
for which lower bounds on the quality of the approximation were easily obtainable [12, 33].
On the other hand, researchers focused on the logical definability of optimization problems and
introduced several syntactically defined classes for which natural completeness results were obtained
[27, 34, 36]: unfortunately, the approximability properties of the problems in these latter
classes were not related to standard complexity-theoretic conjectures. A first step towards the
reconciling of these two approaches consisted of proving lower bounds (modulo P 6= NP or some
other likely condition) on the approximability of complete problems for syntactically defined
classes [1, 31]. More recently, another step has been performed since the closure of syntactically
defined classes with respect to an approximation preserving reducibility has been proved to be
equal to the more familiar computationally defined classes [26].
In spite of this important achievement, beyond APX we are still forced to distinguish between
maximization and minimization problems as long as we are interested in completeness
proofs. Indeed, a result of [27] states that it is not possible to rewrite every NP maximization
problem as an NP minimization problem unless NP=co-NP. A natural question is thus whether
this duality extends to approximation preserving reductions.
Finally, even though the existence of "intermediate" artificial problems, that is, problems
for which lower bounds on their approximation are not obtainable by completeness results
was proved in [12], a natural question arises: do natural intermediate problems exist? Observe
that this question is also open in the field of decision problems: for example, it is known that
the graph isomorphism problem cannot be NP-complete unless the polynomial-time hierarchy
collapses [38], but no result has ever been obtained giving evidence that the problem does not
belong to P.
The first goal of this paper is to define an approximation preserving reducibility that can
be used for as many approximation classes as possible and such that all reductions that have
appeared in the literature still hold. In spite of the fact that the L-reducibility has been the
most widely used so far, we will give strong evidence that it cannot be used to obtain completeness
results in "computationally defined" classes such as APX, log-APX (that is, the class
of problems approximable within a logarithmic factor), and poly-APX (that is, the class of
problems approximable within a polynomial factor). Indeed, on the one hand in [14] it has
been shown that the L-reducibility is too strict and does not allow to reduce some problems
which are known to be easy to approximate to problems which are known to be hard to
approximate. On the other hand in this paper we show that it is too weak and is not approximation
preserving (unless co-NP). The weakness of the L-reducibility is, essentially,
shared by all reducibilities of Fig. 1 but the Strict reducibility and the E-reducibility, while
the strictness of the L-reducibility is shared by all of them (unless P NP ' P NP[O(logn)] ) but the
PTAS-reducibility. The reducibility we propose is a combination of the E-reducibility and of the
PTAS-reducibility and, as far as we know, it is the strictest reducibility that allows to obtain all
approximation completeness results that have appeared in the literature, such as, for example,
the APX-completeness of Maximum Satisfiability [14, 26] and the poly-APX-completeness
of Maximum Clique [26].
The second group of results refers to the existence of natural complete problems for NPO.
Indeed, both [33] and [12] provide examples of natural complete problems for the class of
minimization and maximization NP problems, respectively. In Sect. 3 we will show the existence
of both maximization and minimization NPO-complete natural problems. In particular, we prove
that Maximum Programming and Minimum Programming are NPO-complete.
This result shows that making use of a natural approximation preserving reducibility is enough
powerful to encompass the "duality" problem raised in [27] (indeed, in [26] it was shown
that this duality does not arise in APX, log-APX, poly-APX, and other subclasses of NPO).
Moreover, the same result can also be obtained when restricting ourselves to the class NPO PB
(i.e., the class of polynomially bounded NPO problems). In particular, we prove that Maximum
Programming and Minimum PB Programming are NPO PB-complete.
The third group of results refers to the existence of natural APX-intermediate problems.
In Sect. 4, we will prove that Minimum Bin Packing (and other natural NPO problems)
cannot be APX-complete unless the polynomial-time hierarchy collapses. Since it is well-known
[32] that this problem belongs to APX and that it does not belong to PTAS (that is, the
class of NPO problems with polynomial-time approximation schemes) unless P=NP, our result
yields the first example of a natural APX-intermediate problem (under a natural complexity-theoretic
conjecture). Roughly speaking, the proof of our result is structured into two main
steps. In the first step, we show that if Minimum Bin Packing were APX-complete then the
problem of answering any set of k non-adaptive queries to an NP-complete problem could be
reduced to the problem of approximating an instance of Minimum Bin Packing within a ratio
depending on k. In the second step, we show that the problem of approximating an instance
of Minimum Bin Packing within a given performance ratio can be solved in polynomial-time
by means of a constant number of non-adaptive queries to an NP-complete problem. These
two steps will imply the collapse of the query hierarchy which in turn implies the collapse of
the polynomial-time hierarchy. As a side effect of our proof, we will show that if a problem is
APX-complete, then it does not admit an asymptotic approximation scheme.
The previous results are consequences of new connections between the approximability properties
and the query complexity of NP-hard optimization problems. In several recent papers
the notion of query complexity (that is, the number of queries to an NP oracle needed to solve
a given problem) has been shown to be a very useful tool for understanding the complexity of
approximation problems. In [7, 9] upper and lower bounds have been proved on the number
of queries needed to approximate certain optimization problems (such as Maximum Satisfiability
and Maximum Clique): these results deal with the complexity of approximating the
value of the optimum solution and not with the complexity of computing approximate solu-
tions. In this paper, instead, the complexity of "constructive" approximation will be addressed
by considering the languages that can be recognized by polynomial-time machines which have
a function oracle that solves the approximation problem. In particular, after proving the existence
of natural APX-intermediate problems, in Sect. 4.1 we will be able to solve an open
question of [7] proving that finding the vertices of the largest clique is more difficult than merely
finding the vertices of a 2-approximate clique unless the polynomial-time hierarchy collapses.
The results of [7, 9] show that the query complexity is a good measure to study approximability
properties of optimization problems. The last group of our results show that completeness
in approximation classes implies lower bounds on the query complexity. Indeed, in Sect. 5 we
show that the two approaches are basically equivalent by giving sufficient and necessary conditions
for approximation completeness in terms of query-complexity hardness and combinatorial
properties. The importance of these results is twofold: they give new insights into the structure
of complete problems for approximation classes and they reconcile the approach based
on standard computation models with the approach based on the computation model for approximation
proposed in [8]. As a final observation, our results can be seen as extensions of a
result of [26] in which general sufficient (but not necessary) conditions for APX-completeness
are proved.
1.1. Preliminaries
We assume the reader to be familiar with the basic concepts of computational complexity
theory. For the definitions of most of the complexity classes used in the paper we refer the
reader to one of the books on the subject (see, for example, [2, 5, 16, 35]).
We now give some standard definitions in the field of optimization and approximation theory.
Definition 1. An NP optimization problem A is a fourtuple (I; sol; m; type) such that
1. I is the set of the instances of A and it is recognizable in polynomial time.
2. Given an instance x of I, sol(x) denotes the set of feasible solutions of x. These solutions are
short, that is, a polynomial p exists such that, for any y 2 sol(x), jyj - p(jxj). Moreover, for
any x and for any y with jyj - p(jxj), it is decidable in polynomial time whether y 2 sol(x).
3. Given an instance x and a feasible solution y of x, m(x; y) denotes the positive integer
measure of y (often also called the value of y). The function m is computable in polynomial
time and is also called the objective function.
4. type 2 fmax; ming.
The goal of an NP optimization problem with respect to an instance x is to find an optimum
solution, that is, a feasible solution y such that m(x; sol(x)g. In the
following opt will denote the function mapping an instance x to the measure of an optimum
solution.
The class NPO is the set of all NP optimization problems. Max NPO is the set of maximization
NPO problems and Min NPO is the set of minimization NPO problems.
An NPO problem is said to be polynomially bounded if a polynomial q exists such that, for
any instance x and for any solution y of x, m(x; y) - q(jxj). The class NPO PB is the set of
all polynomially bounded NPO problems. Max PB is the set of all maximization problems in
NPO PB and Min PB is the set of all minimization problems in NPO PB.
Definition 2. Let A be an NPO problem. Given an instance x and a feasible solution y of x,
we define the performance ratio of y with respect to x as
ae m(x; y)
oe
and the relative error of y with respect to x as
The performance ratio (respectively, relative error) is always a number greater than or equal
to 1 (respectively, 0) and is as close to 1 (respectively, 0) as the value of the feasible solution
is close to the optimum value. It is easy to see that, for any instance x and for any feasible
solution y of x,
Definition 3. Let A be an NPO problem and let T be an algorithm that, for any instance
x of A such that sol(x) 6= ;, returns a feasible solution T (x) in polynomial time. Given an
arbitrary function r : N ! [1; 1), we say that T is an r(n)-approximate algorithm for A if the
performance ratio of the feasible solution T (x) with respect to x verifies the following inequality:
Definition 4. Given a class of functions F , an NPO problem A belongs to the class F-APX
if an r(n)-approximate algorithm T for A exists, for some function r 2 F .
In particular, APX, log-APX, poly-APX, and exp-APX will denote the classes F-APX with
F equal to the set O(1), to the set O(log n), to the set O(n O(1) ), and to the set O(2 n O(1)
respectively. One could object that there is no difference between NPO and exp-APX since the
polynomial bound on the computation time of the objective function implies that any NPO
problem is h2 n k -approximable for some h and k. This is not true, since NPO problems exist
for which it is even hard to find a feasible solution. We will see examples of such problems in
Sect. 3 (e.g. Maximum Weighted Satisfiability).
Definition 5. An NPO problem A belongs to the class PTAS if an algorithm T exists such
that, for any fixed rational r ? 1, T (\Delta; r) is an r-approximate algorithm for A.
Clearly, the following inclusions hold:
It is also easy to see that these inclusions are strict if and only if P 6= NP.
1.2. A list of NPO problems
We here define the NP optimization problems that will be used in the paper. For a much larger
list of NPO problems we refer to [11].
Maximum Clique
Instance: Graph E).
Solution: A clique in G, i.e. a subset V 0 ' V such that every two vertices in V 0 are joined
by an edge in E.
Measure: Cardinality of the clique, i.e., jV 0 j.
Maximum Weighted Satisfiability and Minimum Weighted Satisfiability
Instance: Set of variables X, boolean quantifier-free first-order formula OE over the variables
in X, and a weight function
Solution: Truth assignment that satisfies OE.
Measure: The sum of the weights of the true variables.
Maximum Programming and Minimum PB Programming
Instance: Integer m \Theta n-matrix A, integer m-vector b, binary n-vector c.
Solution: A binary n-vector x such that Ax - b.
Measure:
Maximum Satisfiability
Instance: Set of variables X and Boolean CNF formula OE over the variables in X.
Solution: Truth assignment to the variables in X.
Measure: The number of satisfied clauses.
Minimum Bin Packing
Instance: Finite set U of items, and a size s(u) 2 Q " (0; 1] for each u 2 U .
Solution: A partition of U into disjoint sets U Um such that the sum of the sizes of
the items in each U i is at most 1.
Measure: The number of used bins, i.e., the number m of disjoint sets.
Minimum Ordered Bin Packing
Instance: Finite set U of items, a size s(u) 2 Q " (0; 1] for each u 2 U , and a partial order -
on U .
Solution: A partition of U into disjoint sets U Um such that the sum of the sizes of
the items in each U i is at most 1 and if u 2 U i and u
Measure: The number of used bins, i.e., the number m of disjoint sets.
Minimum Degree Spanning Tree
Instance: Graph E).
Solution: A spanning tree for G.
Measure: The maximum degree of the spanning tree.
Minimum Edge Coloring
Instance: Graph E).
Solution: A coloring of E, i.e., a partition of E into disjoint sets
no two edges in E i share a common endpoint in G.
Measure: Cardinality of the coloring, i.e., the number k of disjoint sets.
2. A new approximation preserving reducibility
The goal of this section is to define a new approximation preserving reducibility that can be
used for as many approximation classes as possible and such that all reductions that have
appeared in the literature still hold. We will justify the definition of this new reducibility by
emphasizing the disadvantages of previously known ones. In the following, we will assume that,
for any reducibility, an instance x such that sol(x) 6= ; is mapped into an instance x 0 such that
2.1. The L-reducibility
The first reducibility we shall consider is the L-reducibility (for linear reducibility) [36] which is
often most practical to use in order to show that a problem is at least as hard to approximate
as another.
Definition 6. Let A and B be two NPO problems. A is said to be L-reducible to B, in symbols
A - L B, if two functions f and g and two positive constants ff and fi exist such that:
1. For any x 2 I A , f(x) 2 I B is computable in polynomial time.
2. For any x 2 I A and for any y 2 sol B (f(x)), g(x; y) 2 sol A (x) is computable in polynomial
time.
3. For any x 2 I A , opt B (f(x)) - ffopt A (x).
4. For any x 2 I A and for any y 2 sol B (f(x)),
jopt A
The fourtuple (f; g; ff; fi) is said to be an L-reduction from A to B.
Clearly, the L-reducibility preserves membership in PTAS. Indeed, if (f; g; ff; fi) is an L-
reduction from A to B then, for any x 2 I A and for any y 2 sol B (f(x)), we have that
so that if B 2 PTAS then A 2 PTAS [36]. The above inequality also implies that if A is a
minimization problem and an r-approximate algorithm for B exists, then a (1
approximate algorithm for A exists. In other words, L-reductions from minimization problems
to optimization problems preserve membership in APX. The next result gives a strong evidence
that, in general, this is not true whenever the starting problem is a maximization one.
Theorem 1. The following statements are equivalent:
1. Two problems A 2 Max NPO and B 2 Min NPO exist such that A 62 APX, B 2 APX, and
A - L B.
2. Two Max NPO problems A and B exist such that A 62 APX, B 2 APX, and A - L B.
3. A polynomial-time recognizable set of satisfiable Boolean formulas exists for which no
polynomial-time algorithm can compute a satisfying assignment for each of them.
Proof. (1) ) (2). In this case, it suffices to L-reduce B to a maximization problem C in APX
[26].
Assume that for any polynomial-time recognizable set of satisfiable Boolean
formulas there is a polynomial-time algorithm computing a satisfying assignment for each
formula in the set. Suppose that (f; g; ff; fi) is an L-reduction from a maximization problem
A to a maximization problem B and that B is r-approximable for some r ? 1. Let x be an
instance of A and let y be a solution of f(x) such that opt B (f(x))=mB (f(x); y) - r. For the
sake of convenience, let opt
we have that m x - opt A . We now show that opt A =m x
non-constructive approximation of opt A . Let
. There are two cases.
1. opt B - flopt A . By the definition of the L-reducibility, opt A \Gamma mA - fi(opt
we have that
opt A
Hence,
opt A
r
where the last equality is due to the definition of fl.
2. opt B ? flopt A . It holds that
opt A
Let us now consider the following non-deterministic polynomial-time algorithm.
begin finput: x 2 I A g
compute m x by using the r-approximate algorithm for B and the L-reduction from A to B;
guess y 2 sol A (x);
if mA (x; y) - m x then accept else reject;
By applying Cook's reduction [10] to the above algorithm, it easily follows that, for any
I A , a satisfiable Boolean formula OE x can be constructed in polynomial time in the length
of x so that any satisfying assignment for OE x encodes a solution of x whose measure is at least
Moreover, the set fOE x is recognizable in polynomial time. By assumption, it
is then possible to compute in polynomial time a satisfying assignment for OE x and thus an
approximate solution for x.
Assume that a polynomial-time recognizable set S of satisfiable Boolean formulas
exists for which no polynomial-time algorithm can compute a satisfying assignment
for each of them. Consider the following two NPO problems
fy : y is a truth assignment
to the variables of xg,
jxj if y is a satisfying assignment for x,
and
jxj if y is a satisfying assignment for x,
2jxj otherwise.
Clearly, problem B is in APX, while if A is in APX then there is a polynomial-time algorithm
that computes a satisfying assignment for each formula in S, contradicting the assumption.
Moreover, it is easy to see that A L-reduces to B via f j -x:x, g j -x-y:y,
Observe that in [30] it is shown that the third statement of the above theorem holds if
and only if the fl-reducibility is different from the many-one reducibility. Moreover, in [19]
it is shown that the latter hypothesis is somewhat intermediate between P
and P 6= NP. In other words, there is strong evidence that, even though the L-reducibility is
suitable for proving completeness results within classes contained in APX (such as Max SNP
[36]), this reducibility cannot be used to define the notion of completeness for classes beyond
APX. Moreover, it cannot be blindly used to obtain positive results, that is, to prove the
existence of approximation algorithms via reductions. Finally, it is possible to L-reduce the
maximization problem B defined in the last part of the proof of the previous theorem to
Maximum 3-Satisfiability: this implies that the closure of Max SNP with respect to the
L-reducibility is not included in APX, contrary to what is commonly believed (e.g. see [35],
page 314).
2.2. The E-reducibility
The drawbacks of the L-reducibility are mainly due to the fact that the relation between the
performance ratios is set by two separate linear constraints on both the optimum values and
the absolute errors. The E-reducibility (for error reducibility) [26], instead, imposes a linear
relation directly between the performance ratios.
Definition 7. Let A and B be two NPO problems. A is said to be E-reducible to B, in symbols
A -E B, if two functions f and g and a positive constant ff exist such that:
1. For any x 2 I A , f(x) 2 I B is computable in polynomial time.
2. For any x 2 I A and for any y 2 sol B (f(x)), g(x; y) 2 sol A (x) is computable in polynomial
time.
3. For any x 2 I A and for any y 2 sol B (f(x)),
The triple (f; g; ff) is said to be an E-reduction from A to B.
Observe that, for any function r, an E-reduction maps r(n)-approximate solutions into
solutions where h is a constant depending only on the reduction.
Hence, the E-reducibility not only preserves membership in PTAS but also membership in exp-
APX, poly-APX, log-APX, and APX. As a consequence of this observation and of the results
of the previous section, we have that NPO problems should exist which are L-reducible to each
other but not E-reducible. However, the following result shows that within the class APX the
E-reducibility is just a generalization of the L-reducibility.
Proposition 1. For any two NPO problems A and B, if A - L B and A 2 APX, then A -E B.
Proof. Let T be an r-approximate algorithm for A with r constant and let (f be an
L-reduction from A to B. Then, for any x 2 I A and for any y 2 sol B (f L (x)), EA (x; g L (x;
ff L fi LEB (f L (x); y). If A is a minimization problem then, for any x 2 I A and for any y 2
and thus (f is an E-reduction from A to B. Otherwise (that is, A is a maximization
problem) we distinguish the following two cases.
1. EB (f L (x); y) - 1
: in this case we have that
2. EB (f L
: in this case we have that RB (f L (x);
so that
where the first inequality is due to the fact that T is an r-approximation algorithm for A.
We can thus define a triple (f
1. For any x 2 I A , f
2. For any x 2 I A and for any y 2 sol B (f E (x)),
3. 1)g.
From the above discussion it follows that (f is an E-reduction from A to B. ut
Clearly, the converse of the above result does not hold since no problem in NPO \Gamma NPO PB
can be L-reduced to a problem in NPO PB while any problem in PO can be E-reduced to any
NPO problem. Moreover, in [26] it is shown that Maximum 3-Satisfiability is (NPO PB "
APX)-complete with respect to the E-reducibility. This result is not obtainable by means of
the L-reducibility: indeed, it is easy to prove that Minimum Bin Packing is not L-reducible
to Maximum 3-Satisfiability unless (see, for example, [6]).
The E-reducibility is still somewhat too strict. Indeed, in [14] it has been shown that natural
PTAS problems exist, such as Maximum Knapsack, which are not E-reducible to polynomially
bounded APX problems, such as Maximum 3-Satisfiability (unless a logarithmic
number of queries to an NP oracle is as powerful as a polynomial number of queries).
2.3. The AP-reducibility
The above mentioned drawback of the E-reducibility is mainly due to the fact that an E-
reduction preserves optimum values (see [14]). Indeed, the linear relation between the performance
ratios seems to be too restrictive. According to the definition of approximation preserving
reducibilities given in [12], we could overcome this problem by expressing this relation by means
of an implication. However, this is not sufficient: intuitively, since the function g does not know
which approximation is required, it must still map optimum solutions into optimum solutions.
The final step thus consists of letting the functions f and g depend on the performance ratio 1 .
This implies that different constraints have to be put on the computation time of f and g:
on the one hand, we still want to preserve membership in PTAS, on the other we want the
reduction to be efficient even when poor performance ratios are required. These constraints are
formally imposed in the following definition of approximation preserving reducibility (which is
a restriction of the PTAS-reducibility introduced in [14]).
Definition 8. Let A and B be two NPO problems. A is said to be AP-reducible to B, in
symbols A -AP B, if two functions f and g and a positive constant ff exist such that:
1. For any x 2 I A and for any r ? 1, f(x; r) 2 I B is computable in time t f (jxj; r).
2. For any x 2 I A , for any r ? 1, and for any y 2 sol B (f(x; r)), g(x;
computable in time t g (jxj; jyj; r).
3. For any fixed r, both t f (\Delta; r) and t g (\Delta; \Delta; r) are bounded by a polynomial.
4. For any fixed n, both t f (n; \Delta) and t g (n; n; \Delta) are non-increasing functions.
5. For any x 2 I A , for any r ? 1, and for any y 2 sol B (f(x; r)),
The triple (f; g; ff) is said to be an AP-reduction from A to B.
According to the above definition, functions like 2 1=(r\Gamma1) n h or n 1=(r\Gamma1) are admissible bounds
on the computation time of f and g, while this is not true for functions like n r or 2 n .
We also let the function f depend on the performance ratio because this feature will turn out to be useful
in order to prove interesting characterizations of complete problems for approximation classes.
Observe that, clearly, the AP-reducibility is a generalization of the E-reducibility. Moreover,
it is easy to see that, contrary to the E-reducibility, any PTAS problem is AP-reducible to any
NPO problem.
As far as we know, this reducibility is the strictest one appearing in the literature that allows
to obtain natural APX-completeness results (for instance, the APX-completeness of Maximum
Satisfiability [14, 26]).
3. NPO-complete problems
We will in this section prove that there are natural problems that are complete for the classes
NPO and NPO PB. Previously, completeness results have been obtained just for Max NPO,
Min NPO, Max PB, and Min PB [12, 33, 4, 24]. One example of such a result is the following
theorem.
Theorem 2. Minimum Weighted Satisfiability is Min NPO-complete and Maximum
Weighted Satisfiability is Max NPO-complete, even if only a subset fv of the
variables has nonzero weight w(v i any truth assignment satisfying the instance
gives the value true to at least one v i .
We will construct AP-reductions from maximization problems to minimization problems
and vice versa. Using these reductions we will show that a problem that is Max NPO-complete
or Min NPO-complete in fact is complete for the whole of NPO, and that a problem that is
Max PB-complete or Min PB-complete is complete for the whole of NPO PB.
Theorem 3. Minimum Weighted Satisfiability and Maximum Weighted Satisfiability
are NPO-complete.
Proof. In order to establish the NPO-completeness of Minimum Weighted Satisfiability
we just have to show that there is an AP-reduction from a Max NPO-complete problem to
Minimum Weighted Satisfiability. As the Max NPO-complete problem we will use the
restricted version of Maximum Weighted Satisfiability from Theorem 2.
Let x be an instance of Maximum Weighted Satisfiability, i.e. a formula OE over variables
some variables with weight zero. We will first
give a simple reduction that preserves the approximability within the factor 2, and then adjust
it to obtain an AP-reduction.
Let f(x) be the formula OE - ff is the conjunctive normal form of
are new variables with weights w(z i
where all other variables (even the v-variables) have zero weight. If y is a satisfying assignment
of f(x), let g(x; y) be the restriction of the assignment to the variables that occur in OE. This
assignment clearly satisfies OE.
Note that exactly one of the z-variables is true in any satisfying assignment of f(x). Indeed,
if all z-variables were false, then all v-variables would be false and OE would not be satisfied. On
the other hand, if both z i and z j were true would be both true and false
which is a contradiction. Hence,
In particular this holds for the optimum solution. Thus the performance ratio for Maximum
Weighted Satisfiability is
which means that the reduction preserves the approximability within 2.
Let us now extend the construction in order to obtain R(x; g(x;
for every nonnegative integer k. The reduction described above corresponds to
For any i 2 and for any (b
have a variable z i;b 1 ;:::;b k(i)
. Let
i2f1;:::;sg
(b1 ;:::;b k(i) )2f0;1g k(i)
where ff i;b 1 ;:::;b k(i)
is the conjuctive normal form of
z
as above. Finally, define
(by choosing K greater than 2 k we can disregard the effect of the ceiling operation in the
following computations).
As in the previous reduction exactly one of the z-variables is true in any satisfying assignment
of f k (x). If, in a solution y of f k (x), z i;b 1 ;:::;b
) and we know that
On the other hand, if
s
In both cases, we thus get
and therefore R(x; g(x; Given any r ? 1, if we choose k such that
1). This is obviously an AP-reduction
with 2.
A very similar proof can be used to show that Maximum Weighted Satisfiability is
NPO-complete. ut
Corollary 1. Any Min NPO-complete problem is NPO-complete and any Max NPO-complete
problem is NPO-complete.
As an application of the above corollary, we have that the Minimum Programming
problem is NPO-complete.
We can also show that there are natural complete problems for the class of polynomially
bounded NPO problems.
Theorem 4. Maximum PB Programming and Minimum PB Programming
are NPO PB-complete.
Proof. Maximum Programming is known to be Max PB-complete [4] and Minimum
Programming is known to be Min PB-complete [24]. Thus we just have to show
that there are AP-reductions from Minimum PB Programming to Maximum PB
Programming and from Maximum PB Programming to Minimum PB
Programming.
Both reductions use exactly the same construction. Given a satisfying variable assignment,
we define the one-variables to be the variables occurring in the objective function that have
the value one. The objective value is the number of one-variables plus 1.
The objective value of a solution is encoded by introducing an order of the one-variables.
The order is encoded by a squared number of Fig. 2. The idea is to invert
the objective values, so that a solution without one-variables corresponds to an objective value
of n of the constructed problem, and, in general, a solution with p one-variables corresponds
to an objective value of
size of
solution
one 1 in each row?
only zeros in upper part

Figure

2. The idea of the reduction from Minimum/Maximum PB Programming to Maxi-
mum/Minimum Programming. The variable x j
only if v i is the jth one-variable
in the solution. There is at most one 1 in each column and in each row.
The reductions are constructed as follows. Given an instance of Minimum PB Programming
or Maximum PB i.e. an objective function 1+
some inequalities over variables
and the following inequalities:
most one 1 in each column) (1)
most one 1 in each row) (2)
(only zeros in upper part) (3)
Besides these inequalities we include all inequalities from the original problem, but we substitute
each variable v i with the sum
. The variables in U (that do not occur in the objective
are left intact.
The objective function is defined as
In order to express the objective function with only binary coefficients we have to introduce n
new variables y
1)c. The objective function then is
One can now verify that a solution
of the original problem instance with s one-variables (i.e. with an objective value of s
will exactly correspond to a solution of the constructed problem instance with objective value
vice versa.
Suppose that the optimum solution to the original problem instance has M one-variables,
then the performance ratio (s correspond to the performance ratio
for the constructed problem, where m
n is the relative error due to the floor operation. By
choosing n large enough the relative error can be made arbitrarily small. Thus it is easy to see
that the reduction is an AP-reduction. ut
Corollary 2. Any Min PB-complete problem is NPO PB-complete and any Max PB-complete
problem is NPO PB-complete.
4. Query complexity and APX-intermediate problems
The existence of APX-intermediate problems (that is, problems in APX which are not APX-
complete) has already been shown in [12] where an artificial such problem is obtained by
diagonalization techniques similar to those developed to prove the existence of NP-intermediate
problems [29]. In this section, we prove that "natural" APX-intermediate problems exist: for
instance, we will show that Minimum Bin Packing is APX-intermediate. In order to prove
this result, we will establish new connections between the approximability properties and the
query complexity of NP-hard optimization problems. To this aim, let us first recall the following
definition.
Definition 9. A language L belongs to the class P NP[f(n)] if it is decidable by a polynomial-time
oracle Turing machine which asks at most f(n) queries to an NP-complete oracle, where
n is the input size. The class QH is equal to the union
Similarly, we can define the class of functions FP NP[f(n)] [28]. The following result has been
proved in [21, 22].
Theorem 5. If a constant k exists such that
then the polynomial-time hierarchy collapses.
The query-complexity of the "non-constructive" approximation of several NP-hard optimization
problems has been studied by using hardness results with respect to classes of functions
FP NP[\Delta] [7, 9]. However, this approach cannot be applied to analyze the complexity of
"constructing" approximate solutions. To overcome this limitation, we use a novel approach
that basically consists of considering how helpful is an approximation algorithm for a given
optimization problem to solve decision problems.
Definition 10. Given an NPO problem A and a rational r - 1, A r is a multi-valued partial
function that, given an instance x of A, returns the set of feasible solutions y of x such that
Definition 11. Given an NPO problem A and a rational r - 1, a language L belongs to P A r
if two polynomial-time computable functions f and g exist such that, for any x, f(x) is an
instance of A with sol(f(x)) 6= ;, and, for any y 2 A r (f(x)), g(x; only if x 2 L.
The class AQH(A) is equal to the union
The following result states that an approximation problem does not help more than a
constant number of queries to an NP-complete problem. It is worth observing that, in general,
an approximate solution, even though not very helpful, requires more than a logarithmic number
of queries to be computed [8].
Proposition 2. For any problem A in APX, AQH(A) ' QH.
Proof. Assume that A is a maximization problem (the proof for minimization problems is
similar). Let T be an r-approximate algorithm for A, for some r ? 1, and let L 2 P A ae for some
ae ? 1. Two polynomial-time computable functions f and g then exist witnessing this latter
fact. For any x, let rm. We can then partition
the interval [m; rm] into blog ae rc
and start looking for the subinterval containing the optimum value (a similar technique has
been used in [7, 9]). This can clearly be done using blog ae rc queries to an NP-complete
oracle. One more query is sufficient to know whether a feasible solution y exists whose value
lies in that interval and such that g(x; y) = 1. Since y is ae-approximate, it follows that L can
be decided using blog ae rc queries, that is, L 2 QH. ut
Recall that an NPO problem admits an asymptotic polynomial-time approximation scheme
if an algorithm T exists such that, for any x and for any r ? 1, R(x; T (x;
with k constant and the time complexity of T (x; r) is polynomial with respect to jxj. The
class of problems that admit an asymptotic polynomial-time approximation scheme is usually
denoted by PTAS 1 . The following result shows that, for this class, the previous fact can be
strengthened.
Proposition 3. Let A 2 PTAS 1 . Then a constant h exists such that
Proof. Let A be a minimization problem in PTAS 1 (the proof for maximization problem is
very similar). By definition, a constant k and an algorithm T exist such that, for any instance
x and for any rational r ? 1,
We will now prove that a constant h exists such that, for any r ? 1, a function l r 2 FP NP[h\Gamma1]
exists such that, for any instance x of the problem A,
Intuitively, functions l r form a non-constructive approximation scheme that is computable by
a constant number of queries to an NP-complete oracle. Given an instance x, we can check
whether by means of a single query to an NP oracle, so that we can restrict ourselves
to instances such that sol(x) 6= ; (and thus opt(x) - 1). Note that, for these instances, T (\Delta; 2)
is a 2)-approximate algorithm for A. Let us fix an r ? 1,
and We have to distinguish two cases.
1. a - 2k(k + 2)=": in this case, opt(x) - 2k=", that is, opt(x)"=2 - k. Then
that is, y is an r-approximate solution for x, and we can set l r (in this case l r
has been computed by only one query).
2. a 2)=": in this case, opt(x)
Clearly, dlog k(k queries to NP are sufficient to find the optimum value opt(x) by
means of a binary search technique: in this case l r been computed by
queries.
Let now L be a language in AQH(A), then L 2 P A r for some r ? 1. Let f and g be the
functions witnessing that L 2 P A r . Observe that, for any x, x 2 L if and only if a solution
y for f(x) exists such that m(f(x); y) - l r (f(x)) and g(f(x); 1: that is, given l r (f(x)),
deciding whether x 2 L is an NP problem. Since l r (f(x)) is computable by means of at most
queries to NP, we have that 2. ut
The next proposition, instead, states that any language L in the query hierarchy can be
decided using just one query to A r where A is APX-complete and r depends on the level of
the query hierarchy L belongs to. In order to prove this proposition, we need the following
technical result 2 .
2 Recall that the NP-complete problem Partition is defined as follows: given a set U of items and a size
does there exists a subset U 0 ' U such that
Lemma 1. For any APX-complete problem A and for any k, two polynomial-time computable
functions f and g and a constant r exist such that, for any k-tuple of instances of
Partition, is an instance of A and if y is a solution of x whose performance
ratio is smaller than r then g(x; only if x i
is a yes-instance.
Proof. Let x be an instance of Partition for loss of generality,
we can assume that the U i s are pairwise disjoint and that, for any i,
2. Let
s; -) be an instance of Minimum Ordered Bin Packing defined as follows (a
similar construction has been used in [37]).
1.
where the v i s are new items.
2. For any u 2 U i ,
3. For any i ! j - k, for any u 2 U i , and for any u
Any solution of w must be formed by a sequence of packings of U such that, for
any i, the bins used for U i are separated by the bins used for U i+1 by means of one bin which
is completely filled by v i . In particular, the packings of the U i s in any optimum solution must
use either two or three bins: two bins are used if and only if x i is a yes-instance. The optimum
measure thus is at most 4k \Gamma 1 so that any (1 + 1=(4k))-approximate solution is an optimum
solution.
Since Minimum Ordered Bin Packing belongs to APX [41] and A is APX-complete,
then an AP-reduction (f exists from Minimum Ordered Bin Packing to A. We can
then define 1+1=(4ffk). For any r-approximate
solution y of x, the fourth property of the AP-reducibility implies that
is a (1 1=(4k))-approximate solution of w and thus an optimum solution of w. From z, we
can easily derive the right answers to the k queries x
We are now able to prove the following result.
Proposition 4. For any APX-complete problem A, QH ' AQH(A).
Proof. Let some h. It is well known (see, for instance, [3])
that L can be reduced to the problem of answering non-adaptive queries to NP.
More formally, two polynomial-time computable functions t 1 and t 2 exist such that, for any x,
are k instances of the Partition problem, and for any
(b 1g. Moreover, if, for any j, b only if x j
is a yes-instance, then t 2 only if x 2 L.
Let now f , g and r be the two functions and the constant of Lemma 1 applied to problem A
and constant k. For any x, x is an instance of A such that if y is an r-approximate
solution for only if x 2 L. Thus, L 2 P A r . ut
By combining Propositions 2 and 4, we thus have the following theorem that characterizes
the approximation query hierarchy of the hardest problems in APX.
Theorem 6. For any APX-complete problem A,
Finally, we have the following result that states the existence of natural intermediate problems
in APX.
Theorem 7. If the polynomial-time hierarchy does not collapse, then Minimum Bin Packing,
Minimum Degree Spanning Tree, and Minimum Edge Coloring are APX-intermediate.
Proof. From Proposition 3 and from the fact that Minimum Bin Packing is in PTAS 1 [25], it
follows that AQH(Minimum Bin Packing) ' P NP[h] for a given h. If Minimum Bin Packing
is APX-complete, then from Proposition 4 it follows that QH ' P NP[h] . From Theorem 5 we
thus have the collapse of the polynomial-time hierarchy. The proofs for Minimum Degree
Spanning Tree and Minimum Edge Coloring are identical and use the results of [18, 15].
ut
Observe that the previous result does not seem to be obtainable by using the hypothesis
shown by the following theorem.
Theorem 8. If Packing is APX-complete.
Proof. Assume present an AP reduction from Maximum Satisfiability
to Minimum Bin Packing. Since Turing
machine M exists that, given in input an instance OE of Maximum Satisfiability, has an
accepting computation and all accepting computations halt with an optimum solution for OE
written on the tape. Indeed, M guesses an integer k, an assigment - such that m(OE;
a proof of the fact that opt(OE) - k. From the proof of Cook's theorem it follows that, given OE, we
can find in polynomial time a formula OE 0 such that OE 0 is satisfiable and that given any satisfying
assignment for OE 0 we can find in polynomial time an optimum solution for OE. By combining
this construction with the NP-completeness proof of the Minimum Bin Packing problem, we
obtain two polynomial-time computable functions t 1 and t 2 such that, for any instance OE of
Maximum Satisfiability, t 1 is an instance of Minimum Bin Packing such that
optimum solution y of x OE , t 2 is an optimum solution of OE.
Observe that, by construction, an r-approximate solution for x OE is indeed an optimum solution
provided that r ! 3=2. Let T be a 4/3-approximate algorithm for Maximum Satisfiability
[42, 17]. The reduction from Maximum Satisfiability to Minimum Bin Packing is defined
as follows: f(OE;
It is immediate to verify that the above is an AP-reduction with
Finally, note that the above result can be extended to any APX problem which is NP-hard
to approximate within a given performance ratio.
4.1. A remark on Maximum Clique
The following lemma is the analogoue of Proposition 2 within NPO PB and can be proved
similarly by binary search techniques.
Lemma 2. For any NPO PB problem A and for any r ? 1, P A r ' P NP[log logn+O(1)] .
From this lemma, from the fact that P NP[logn] is contained in P MC 1 where MC stands for
Maximum Clique [28], and from the fact that if a constant k exists such that
then the polynomial-time hierarchy collapses [40], it follows the next result that solves an open
question posed in [7]. Informally, this result states that it is not possible to reduce the problem
of finding a maximum clique to the problem of finding a 2-approximate clique (unless the
polynomial-time hierarchy collapses).
Theorem 9. If P MC then the polynomial-time hierarchy collapses.
5. Query complexity and completeness in approximation classes
In this final section, we shall give a full characterization of problems complete for poly-APX
and for APX, respectively, in terms of hardness of the corresponding approximation problems
with respect to classes of partial multi-valued functions and in terms of suitably defined
combinatorial properties.
The classes of functions we will refer to have been introduced in [8] as follows.
Definition 12. FNP NP[q(n)] is the class of partial multi-valued functions computable by non-deterministic
polynomial-time Turing machines which ask at most q(n) queries to an NP oracle
in the entire computation tree. 3
In order to talk about hardness with respect to these classes we will use the following
reducibility which is an extension of both metric reducibility [28] and one-query reducibility
[13] and has been introduced in [8].
Definition 13. Let F and G be two partial multi-valued functions. We say that F many-one
reduces to G (in symbols, F-mvG) if two polynomial-time algorithms t 1 and t 2 exist such
that, for any x in the domain of F , t 1 (x) is in the domain of G and, for any y 2 G(t 1 (x)),
The combinatorial property used to characterize poly-APX-complete problems is the well-known
self-improvability (see, for instance, [34]).
Definition 14. A problem A is self-improvable if two algorithms t 1 and t 2 exist such that, for
any instance x of A and for any two rationals r is an instance of A
and, for any y 0 2 A r 2
(x). Moreover, for any fixed r 1 and r 2 , the
running time of t 1 and t 2 is polynomial.
We are now ready to state the first result of this section.
Theorem 10. A poly-APX problem A is poly-APX-complete if and only if it is self-improvable
and A r 0
is FNP NP[log log n+O(1)] -hard for some r 0 ? 1.
Proof. Let A be a poly-APX-complete problem. Since Maximum Clique is self-improvable
[16] and poly-APX-complete [26] and since the equivalence with respect to the AP-reducibility
preserves the self-improvability property (see [34]), we have that A is self-improvable. It is then
sufficient to prove that A 2 is hard for FNP NP[log logn+O(1)] .
From the poly-APX-completeness of A we have that Maximum Clique -AP A: let ff
be the constant of this reduction. From Theorem 12 of [8] we have that any function F in
FNP NP[log log n+O(1)] many-one reduces to Maximum Clique 1+ff . From the definition of AP-
reducibility, we also have that Maximum Clique 1+ff -mvA 2 so that F many-one reduces to
A 2 .
Conversely, let A be a poly-APX self-improvable problem such that, for some r 0 , A r 0
is FNP NP[loglogn+O(1)] -hard. We will show that, for any problem B in poly-APX, B is
AP-reducible to A. To this aim, we introduce the following partial multi-valued function
multisat: given in input a sequence (OE instances of the satisfiability problem with
and such that, for any i, if OE i+1 is satisfiable then OE i is satisfiable, a possible
output is a satisfying truth-assignment for OE i   where i
the proof of Theorem 12 of [8] it follows that this function is FNP NP[loglogn+O(1)] -complete.
3 We say that a multi-valued partial function F is computable by a nondeterministic Turing machine N if,
for any x in the domain of F , an halting computation path of N(x) exists and any halting computation path of
outputs a value of F (x).
By making use of techniques similar to those of the proof of Proposition 2, it is easy to see
that, since B is in poly-APX, two algorithms t B
2 exist such that, for any fixed r ? 1,
many-one reduction from B r to multisat. Moreover, since A r0 is
FNP NP[log log n+O(1)] -hard, then a many-one reduction (t M
exists from multisat to A r 0
Finally, let t A
2 be the functions witnessing the self-improvability of A.
The AP-reduction from B to A can then be derived as follows:
\Gamma\Gamma\Gamma\Gamma\Gamma\Gamma\Gamma\Gamma\Gamma\Gamma\Gamma! x 00
\Gamma\Gamma\Gamma\Gamma\Gamma\Gamma\Gamma\Gamma\Gamma\Gamma\Gamma! x 000
y
It is easy to see that if y 000 is an r-approximate solution for the instance x 000 of A, then y is an
r-approximate solution of the instance x of B. That is, B is AP-reducible to A with
The above theorem cannot be proved without the dependency of both f and g on r in the
definition of AP-reducibility. Indeed, it is possible to prove that if only g has this property
then, unless the polynomial-time hierarchy collapses, a self-improvable problem A exists such
that A 2 is FNP NP[loglogn+O(1)] -hard and A is not poly-APX-complete.
In order to characterize APX-complete problems, we have to define a different combinatorial
property. Intuitively, this property states that it is possible to merge several instances into one
instance in an approximation preserving fashion.
Definition 15. An NPO problem A is linearly additive if a constant fi and two algorithms
exist such that, for any rational r ? 1 and for any sequence x of instances
of A, x r) is an instance of A and, for any y 0 2 A 1+(r\Gamma1)fi=k
each y i is an r-approximate solution of x i . Moreover, the
running time of t 1 and t 2 is polynomial for every fixed r.
Theorem 11. An APX problem A is APX-complete if and only if it is linearly additive and
a constant r 0 exists such that A r0 is FNP NP[1] -hard.
Proof. Let A be an r A -approximable APX-complete problem. From the proof of Proposition 4 a
constant r 0 exists such that A r 0
is hard for FNP NP[1] . In order to prove the linear additivity, fix
any r ? 1 and let x be instances of A. Without loss of generality, we can assume r ! r A
(otherwise the k instances can be r-approximated by using the r A -approximate algorithm).
For any the problem of finding an r-approximate solution y i for x i is reducible
to the problem of constructively solving a set of dlog r r A e instances of Partition. Observe
that dlog r r A e - c=(r \Gamma 1) for a certain constant c depending on r A . Moreover, we claim that a
constant fl exists such that constructively solving kc=(r \Gamma 1) instances of Partition is reducible
to 1)=kc)-approximating a single instance of A (indeed, this can be shown along the
lines of the proof of Proposition 4). That is, A is linearly additive with
Conversely, let A be a linearly additive APX problem such that A r0 is FNP NP[1] -hard for
some r 0 and let B be an r B -approximable problem. Given an instance x of B, for any r ?
1 we can reduce the problem of finding an r-approximate solution for x to the problem of
constructively solving c=(r \Gamma 1) instances of Partition, for a proper constant c not depending
on r. Each of these questions is reducible to A r 0
, since any NP problem can be constructively
solved by an FNP NP[1] function. From linear additivity, it follows that r 0 -approximating c=(r\Gamma1)
instances of A is reducible to (1 1)=c)-approximating a single instance of A.
This is an AP-reduction from B to A with
Note that linear additivity plays for APX more or less the same role of self-improvability for
poly-APX. These two properties are, in a certain sense, one the opposite of the other: while the
usefulness of APX-complete approximation problems to solve decision problems depends on the
performance ratio and does not depend on the size of the instance, the usefulness of poly-APX-
complete approximation problems depends on the size of the instance and does not depend
on the performance ratio. Indeed, it is possible to prove that no APX-complete problem can
be self-improvable (unless and that no poly-APX-complete problem can be linearly
additive (unless the polynomial-time hierarchy collapses).
It is now an interesting question to find a characterizing combinatorial property of log-APX-
complete problems. Indeed, we have not been able to establish this characterization: at present,
we can only state that it cannot be based on the self-improvability property as shown by the
following result.
Theorem 12. No log-APX-complete problem can be self-improvable unless the polynomial-time
hierarchy collapses.
Proof. Let us consider the optimization problem Max Number of Satisfiable Formulas
(in short, MNSF) defined as follows.
Instance: Set of m boolean formulas OE in 3CNF, such that OE 1 is a tautology and
is the size of the input instance.
Solution: Truth assignment - to the variables of OE
Measure: The number of satisfied formulas, i.e., jfi : OE i is satisfied by -gj.
Clearly, MNSF is in log-APX, since the measure of any assignment - is at least 1, and the
optimum value is always smaller than log n, where n is the size of the input. We will show that,
for any r ! 2, MNSF r is hard for FNP NP[log loglog n\Gamma1] .
Given log log n queries to an NP-complete language (of size polynomial in n) x
we can construct an instance of MNSF where OE 1 is a tautology and, for i - 1,
the formulas OE are satisfiable if and only if at least i instances among
are yes-instances (these formulas can be easily constructed using the standard
proof of Cook's theorem). Note that adding dummy clauses to some
formulas, we can achieve the bound m - log jOE j. Moreover, from an r-approximate
solution for \Phi we can decide how many instances in x log logn are yes-instances, and we
can also recover solutions for such instances. That is, any function in FNP NP[loglog logn\Gamma1] is
many-one reducible to MNSF r .
Let A be a self-improvable log-APX-complete problem. Then, for any function F 2
FNP NP[log log logn\Gamma1] , F-mvMNSF 1:5 -mvA 1+ff=2 -mvA 2 16 where ff is the constant in the AP-
reduction from MNSF to A and where the last reduction is due to the self-improvability of
A. Thus, for any x, computing F (x) is reducible to finding a 2 16 -approximate solution for an
instance x 0 with jx 0 j - jxj c for a certain constant c. Since A 2 log-APX, it is possible to find
in polynomial time a (k log jx 0 j)-approximate solution y for x 0 where k is a constant. From
y, by means of binary search techniques, we can find a 2 16 -approximate solution for x 0 using
adaptive queries to NP where
the last inequality surely holds for sufficiently large jxj. Thus,
FNP NP[log loglog n\Gamma1] ' FNP NP[loglog logn\Gamma2]
which implies the collapse of the polynomial-time hierarchy [40]. ut
As a consequence of the above theorem and of the results of [26], we conjecture that the
minimum set cover problem is not self-improvable.


--R

"Proof verification and hardness of approximation problems"
Structural complexity I.
"Bounded queries to SAT and the Boolean hierarchy"
"On the complexity of approximating the independent set problem"
Introduction to the theory of complexity.

"On the query complexity of clique size and maximum satisfiability"
"A machine model for NP-approximation problems and the revenge of the Boolean hierarchy"
"On bounded queries and approximation"
"The complexity of theorem proving procedures"
"A compendium of NP optimization problems"
"Completeness in approximation classes"
"Relative Complexity of Evaluating the Optimum Cost and Constructing the Optimum for Maximization Problems"
"On approximation scheme preserving reducibility and its applications"
"Approximating the minimum degree spanning tree to within one from the optimal degree"
Computers and intractability: a guide to the theory of NP-completeness
"New 3/4-approximation algorithms for the maximum satisfiability problem"
"The NP-completeness of edge-coloring"
"Decision trees and downward closures"
"Approximation algorithms for combinatorial problems"
"The polynomial time hierarchy collapses if the Boolean hierarchy collapses"
"ERRATUM: The Polynomial Time Hierarchy Collapses if the Boolean Hierarchy Collapses"
On the approximability of NP-complete optimization problems
"Polynomially bounded minimization problems that are hard to approximate"
"An efficient approximation scheme for the one-dimensional bin packing problem"
"On syntactic versus computational views of approximability"
"Approximation properties of NP minimization classes"
"The complexity of optimization problems"
"On the structure of polynomial-time reducibility"
"On fl-reducibility versus polynomial time many-one reducibility"
"On the hardness of approximating minimization problems"
"Lecture notes on approximation algorithms"
"On approximation preserving reductions: Complete problems and robust measures"
"Quantifiers and approximation"
Computational complexity.
"Optimization, approximation, and complexity classes"
"Bounds for assembly line balancing heuristics"
"Graph isomorphism is in the low hierarchy"
"Continuous reductions among combinatorial optimization problems"
"Bounded query computations"
"Assembly line balancing as generalized bin packing"
"On the approximation of maximum satisfiability"
--TR

--CTR
Taneli Mielikinen , Esko Ukkonen, The complexity of maximum matroid-greedoid intersection and weighted greedoid maximization, Discrete Applied Mathematics, v.154 n.4, p.684-691, 15 March 2006
Tapio Elomaa , Matti Kriinen, The Difficulty of Reduced Error Pruning of Leveled Branching Programs, Annals of Mathematics and Artificial Intelligence, v.41 n.1, p.111-124, May 2004
Andreas Bley, On the complexity of vertex-disjoint length-restricted path problems, Computational Complexity, v.12 n.3-4, p.131-149, September 2004
Bruno Escoffier , Vangelis Th. Paschos, Completeness in approximation classes beyond APX, Theoretical Computer Science, v.359 n.1, p.369-377, 14 August 2006
approximation algorithms;complexity classes;reducibilities