On Syntactic versus Computational Views of Approximability.
We attempt to reconcile the two distinct views of approximation classes: syntactic and computational. Syntactic classes such as MAX SNP permit structural results and have natural complete problems, while computational classes such as APX allow us to work with classes of problems whose approximability is well understood. Our results provide a syntactic characterization of computational classes and give a computational framework for syntactic classes.We compare the syntactically defined class MAX SNP with the computationally defined class APX and show that every problem in APX can be "placed" (i.e., has approximation-preserving reduction to a problem) in MAX SNP.  Our methods introduce a simple, yet general, technique for creating approximation-preserving reductions which shows that any "well"-approximable problem can be reduced in an approximation-preserving manner to a problem which is hard to approximate to corresponding factors. The reduction then follows easily from the recent nonapproximability results for MAX SNP-hard problems. We demonstrate the generality of this technique by applying it to other classes such as MAX SNP-RMAX(2) and MIN F$^{+}\Pi_2(1)$ which have the clique problem and the set cover problem, respectively, as complete problems.The syntactic nature of MAX SNP was used by Papadimitriou and Yannakakis [J. Comput. System Sci., 43 (1991), pp. 425--440] to provide approximation algorithms for every problem in the class. We provide an alternate approach to demonstrating this result using the syntactic nature of MAX SNP. We develop a general paradigm, nonoblivious local search, useful for developing simple yet efficient approximation algorithms. We show that such algorithms can find good approximations for all MAX SNP problems, yielding approximation ratios comparable to the best known for a variety of specific MAX SNP-hard problems. Nonoblivious local search provably outperforms standard local search in both the degree of approximation achieved and the efficiency of the resulting algorithms.
Introduction
The approximability of NP optimization (NPO) problems has been investigated in the past via the definition
of two different types of problem classes: syntactically-defined classes such as MAX SNP, and
computationally-defined classes such as APX (the class of optimization problems to which a constant factor
approximation can be found in polynomial time). The former is useful for obtaining structural results
and has natural complete problems, while the latter allows us to work with classes of problems whose
approximability is completely determined. We attempt to develop linkages between these two views of
approximation problems and thereby obtain new insights about both types of classes. We show that a
natural generalization of MAX SNP renders it identical to the class APX. This is an unexpected validation
of Papadimitriou and Yannakakis's definition of MAX SNP as an attempt at providing a structural basis
to the study of approximability. As a side-effect, we resolve the open problem of identifying complete
problems for MAX NP. Our techniques extend to a generic theorem that can be used to create an approximation
hierarchy. We also develop a generic algorithmic paradigm which is guaranteed to provide good
approximations for MAX SNP problems, and may also have other applications.
1.1 Background and Motivation
A wide variety of classes are defined based directly on the polynomial-time approximability of the problems
contained within, e.g., APX (constant-factor approximable problems), PTAS (problems with polynomial-time
approximation schemes), and FPTAS (problems with fully-polynomial-time approximation schemes).
The advantage of working with classes defined using approximability as the criterion is that it allows us to
work with problems whose approximability is well-understood. Crescenzi and Panconesi [9] have recently
also been able to exhibit complete problems for such classes, particularly APX. Unfortunately such complete
problems seem to be rare and artificial, and do not seem to provide insight into the more natural problems
in the class. Research in this direction has to find approximation-preserving reductions from the known
complete but artificial problems in such classes to the natural problems therein, with a view to understanding
the approximability of the latter.
The second family of classes of NPO problems that have been studied are those defined via syntactic
considerations, based on a syntactic characterization of NP due to Fagin [10]. Research in this direction,
initiated by Papadimitriou and Yannakakis [22], and followed by Panconesi and Ranjan [21] and Kolaitis
and Thakur [19], has led to the identification of approximation classes such as MAX SNP, RMAX(2), and
(1). The syntactic prescription in the definition of these classes has proved very useful in the
establishment of complete problems. Moreover, the recent results of Arora, Lund, Motwani, Sudan, and
Szegedy [3] have established the hardness of approximating complete problems for MAX SNP to within
(specific) constant factors unless It is natural to wonder why the hardest problems in this syntactic
sub-class of APX should bear any relation to all of NP.
Though the computational view allows us to precisely classify the problems based on their approxima-
bility, it does not yield structural insights into natural questions such as: Why certain problems are easier
to approximate than some others? What is the canonical structure of the hardest representative problems
of a given approximation class? and, so on. Furthermore, intuitively speaking, this view is too abstract to
identification of, and reductions to establish, natural complete problems for a class. The syntactic
view, on the other hand, is essentially a structural view. The syntactic prescription gives a natural way of
identifying canonical hard problems in the class and performing approximation-preserving reductions to
establish complete problems.
Attempts at trying to find a class with both the above mentioned properties, i.e., natural complete
problems and capturing all problems of a specified approximability, have not been very successful. Typically
the focus has been to relax the syntactic criteria to allow for a wider class of problems to be included in
the class. However in all such cases it seems inevitable that these classes cannot be expressive enough to
encompass all problems with a given approximability. This is because each of these syntactically defined
approximation classes is strictly contained in the class NPO; the strict containment can be shown by syntactic
considerations alone. As a result if we could show that any of these classes contains all of P, then we would
have separated P from NP. We would expect that every class of this nature would be missing some problems
from P, and this has indeed been the case with all current definitions.
We explore a different direction by studying the structure of the syntactically defined classes when we
look at their closure under approximation-preserving reductions. The advantage of this is that the closure
maintains the complete problems of the set, while managing to include all of P into the closure (for problems
in P, the reduction is to simply use a polynomial time algorithm to compute an exact solution). It now
becomes interesting, for example, to compare the closure 1 of MAX SNP (denoted MAX SNP) with APX.
A positive resolution, i.e., MAX would immediately imply the non-existence of a PTAS for
MAX SNP-hard problems, since it is known that PTAS is a strict subset of APX, if P 6= NP. On the other
hand, an unconditional negative result would be difficult to obtain, since it would imply P 6= NP.
Here we resolve this question in the affirmative. The exact nature of the result obtained depends upon the
precise notion of an approximation preserving reduction used to define the closure of the class MAX SNP.
The strictest notion of such reductions available in the literature are the L-reductions due to Papadimitriou
and Yannakakis [22]. We introduce a new notion of reductions, called E-reductions, which are a slight
extension of L-reductions. Using such reductions to define the class MAX SNP we show that this equals
APX-PB, the class of all polynomially bounded NP optimization problems which are approximable to
within constant factors. By using slightly looser definitions of approximation preserving reductions (and
in particular the PTAS-reductions of Crescenzi et al [8]) this can be extended to include all of APX into
MAX SNP. We then build upon this result to identify an interesting hierarchy of such approximability
classes. An interesting side-effect of our results is the positive answer to the question of Papadimitriou and
Yannakakis [22] about whether MAX NP has any complete problems.
The syntactic view seems useful not only in obtaining structural complexity results but also in developing
paradigms for designing efficient approximation algorithms. Exploiting the syntactic nature of MAX SNP,
we develop a general paradigm for designing good approximation algorithms for problems in that class
and thereby provide a more computational view of it. We refer to this paradigm as non-oblivious local
search, and it is a modification of the standard local search technique [24]. We show that every MAX SNP
problem can be approximated to within constant factors by such algorithms. It turns out that the performance
of non-oblivious local search is comparable to that of the best-known approximation algorithms for
several interesting and representative problems in MAX SNP. An intriguing possibility is that this is not a
coincidence, but rather a hint at the universality of the paradigm or some variant thereof.
Our results are related to some extent to those of Ausiello and Protasi [4]. They define a class GLO
(for Guaranteed Local Optima) of NPO problems which have the property that for all locally optimum
solutions, the ratio between the value of the global and the local optimum is bounded by a constant. It
follows that GLO is a subset of APX, and it was shown that it is in fact a strict subset. We show that
a MAX SNP problem is not contained in GLO, thereby establishing that MAX SNP is not contained in
GLO. This contrasts with our notion of non-oblivious local search which is guaranteed to provide constant
factor approximations for all problems in MAX SNP. In fact, our results indicate that non-oblivious local
search is significantly more powerful than standard local search in that it delivers strictly better constant
ratios, and also will provide constant factor approximations to problems not in GLO. Independently of our
work, Alimonti [1] has used a similar local search technique for the approximation of a specific problem
not contained in GLO or MAX SNP.
1 Papadimitriou and Yannakakis [22] hinted at the definition of MAX SNP by stating that: minimization problems will be
"placed" in the classes through L-reductions to maximization problems.
1.2 Summary of Results
In Section 2, we present the definitions required to state our results, and in particular the definitions of an E-
reduction, APX, APX-PB, MAX SNP and MAX SNP. In Section 3, we show that MAX
A generic theorem which allows to equate the closure of syntactic classes to appropriate computational
classes is outlined in Section 4; we also develop an approximation hierarchy based on this result.
The notion of non-oblivious local search and NON-OBLIVIOUS GLO is developed in Section 5. In
Section 6, we illustrate the power of non-obliviousness by first showing that oblivious local search can
achieve at most the performance ratio 3=2 for MAX 2-SAT, even if it is allowed to search exponentially
large neighborhoods; in contrast, a very simple non-oblivious local search algorithm achieves a performance
ratio of 4=3. We then establish that this paradigm yields a 2 k approximation to MAX k-SAT. In
Section 7, we provide an alternate characterization of MAX SNP via a class of problems called MAX k-CSP.
It is shown that a simple non-oblivious algorithm achieves the best-known approximation for this problem,
thereby providing a uniform approximation for all of MAX SNP. In Section 8, we further illustrate the power
of this class of algorithms by showing that it can achieve the best-known ratio for a specific MAX SNP
problem and for VERTEX COVER (which is not contained in GLO). This implies that MAX SNP is not
contained in GLO, and that GLO is strict subset of NON-OBLIVIOUS GLO. In Section 9, we apply it to
approximating the traveling salesman problem. Finally, in Section 10, we apply this technique to improving
a long-standing approximation bound for maximum independent sets in bounded-degree graphs.
A preliminary version of this paper appeared in [18].
Preliminaries and Definitions
Given an NPO problem P and an instance I of P, we use jIj to denote the length of I and OPT (I) to
denote the optimum value for this instance. For any solution S to I, the value of the solution, denoted
by V (I; S), is assumed to be a polynomial time computable function which takes positive integer values
(see [7] for a precise definition of NPO).
solution S to an instance I of an NPO problem P has error E(I;
Notice that the above definition of error applies uniformly to the minimization and maximization
problems at all levels of approximability.
(Performance Ratio) An approximation algorithm A for an optimization problem P has
performance ratio R(n) if, given an instance I of P with
oe
A solution of value within a multiplicative factor r of the optimal value is referred to as an r-approximation.
The performance ratio for A is R if it always computes a solution with error at most R \Gamma 1.
2.1 E-reductions
We now describe the precise approximation preserving reduction we will use in this paper. Various other
notions of approximation preserving reductions exist in the literature (cf. [2, 16]) but the reduction which
we use, referred to as the E-reduction (for error-preserving reduction), seems to be the strictest. As we will
see, the E-reduction is essentially the same as the L-reduction of Papadimitriou and Yannakakis [22] and
differs from it in only one relatively minor aspect.
problem P E-reduces to a problem P 0 (denoted exist
polynomial time computable functions f , g and a constant fi such that
maps an instance I of P to an instance I 0 of P 0 such that OPT (I) and OPT are related by a
polynomial factor,
maps solutions S 0 of I 0 to solutions S of I such that
E(I;
Remark 1 An E-reduction is essentially the strictest possible notion of reduction. It requires that the error
for P be linearly related to the error for P 0 . Most other notions of reductions in the literature, for example
the F -reductions and P -reductions of Crescenzi and Panconesi [9], do not enforce this condition. One
important consequence of this constraint is that E-reductions are sensitive, i.e., when I 2 P is mapped
to I under an E-reduction then a good solution to I 0 should provide structural information about
a good solution to I. Thus, reductions from real optimization problems to decision problems artificially
encoded as optimization problems are implausible.
Having P /E P 0 implies that P is as well approximable as P 0 ; in fact, an E-reduction is an
FPTAS-preserving reduction. An important benefit is that this reduction can applied uniformly at all levels
of approximability. This is not the case with the other existing definitions of FPTAS-preserving reduction in
the literature. For example, the FPTAS-preserving reduction of Crescenzi and Panconesi [9]
is much more unrestricted in scope and does not share this important property of the E-reduction. Note
that Crescenzi and Panconesi [9] showed that there exists a problem P 0 2 PTAS such that for any problem
. Thus, there is the undesirable situation that a problem P with no PTAS has a
FPTAS-preserving reduction to a problem P 0 with a PTAS.
Remark 3 The L-reduction of Papadimitriou and Yannakakis [22] enforces the condition that the optima of
an instance I of P be linearly related to the optima of the instance I 0 of P 0 to which it is mapped. This appears
to be an unnatural restriction considering that the reduction itself is allowed to be an arbitrary polynomial
time computation. This is the only real difference between their L-reduction and our E-reduction, and an
E-reduction in which the linearity relation of the optimas is satisfied is an L-reduction. Intuitively, however,
in the study of approximability the desirable attribute is simply that the errors in the corresponding solutions
are closely (linearly) related. The somewhat artificial requirement of a linear relation between the optimum
values precludes reductions between problems which are related to each other by some scaling factor. For
instance, it seems desirable that two problems whose objective functions are simply related by any fixed
polynomial factor should be inter-reducible under any reasonable definition of an approximation-preserving
reduction. Our relaxation of the L-reduction constraint is motivated precisely by this consideration.
Let C be any class of NPO problems. Using the notion of an E-reduction, we define hardness and
completeness of problems with respect C, as well its closure and polynomially-bounded sub-class.
Definition 4 (Hard and Complete Problems) A problem P 0 is said to be C-hard if for all problems
we have P /E P 0 . A C-hard problem P is said to be C-complete if in addition P 2 C.
Definition 5 (Closure) The closure of C, denoted by C, is the set of all NPO problems P such that P /E P 0
for some P 0 2 C.
Remark 4 The closure operation maintains the set of complete problems for a class.
Definition 6 (Polynomially Bounded Subset) The polynomially bounded subset of C, denoted C-PB, is
the set of all problems P 2 C for which there exists a polynomial p(n) such that for all instances I 2 P,
2.2 Computational and Syntactic Classes
We first define the basic computational class APX.
Definition 7 (APX) An NPO problem P is in the class APX if there exists a polynomial time computable
function A mapping instances of P to solutions, and a constant c - 1, such that for all instances I of P,
The class APX-PB consists of all polynomially bounded NPO problems which can be approximated
within constant factors in polynomial time.
If we let F-APX denote the class of NPO problems that are approximable to within a factor F , then
we obtain a hierarchy of approximation classes. For instance, poly-APX and log-APX are the classes of
NPO problems which have polynomial time algorithms with performance ratio bounded polynomially and
logarithmically, respectively, in the input length. A more precise form of these definitions are provided in
Section 4.
Let us briefly review the definition of some syntactic classes.
Definition 8 (MAX SNP and MAX NP [22]) MAX SNP is the class of NPO problems expressible as finding
the structure S which maximizes the objective function
denotes the input (consisting of a finite universe U and a finite set of bounded arity
predicates P ), S is a finite structure, and F is a quantifier-free first-order formula. The class MAX NP is
defined analogously except the objective function is
A natural extension is to associate a weight with every tuple in the range of the universal quantifier; the
modified objective is to find an S which maximizes V (I;
~x w(~x)F(I;
the weight associated with the tuple ~x.
Example 1 (MAX k-SAT) The MAX k-SAT problem is: given a collection of m clauses on n boolean
variables where each (possibly weighted) clause is a disjunction of precisely k literals, find a truth assignment
satisfying a maximum weight collection of clauses. For any fixed integer k, MAX k-SAT belongs to the
class MAX SNP. The results of Papadimitriou and Yannakakis [22] can be adapted to show that for k - 2,
MAX k-SAT is complete under E-reductions for the class MAX SNP.
Definition 9 (RMAX(k) [21]) RMAX(k) is the class of NPO problems expressible as finding a structure
which maximizes the objective function
where S is a single predicate and F(I; S; ~y) is a quantifier-free CNF formula in which S occurs at most k
times in each clause and all its occurrences are negative.
The results of Panconesi and Ranjan [21] can be adapted to show that MAX CLIQUE is complete under
E-reductions for the class RMAX(2).
is the class of NPO problems expressible as finding a
structure S which minimizes the objective function
where S is a single predicate, F(I; S; ~y) is a quantifier-free CNF formula in which S occurs at most k times
in each clause and all its occurrences are positive.
The results of Kolaitis and Thakur [19] can be adapted to show that SET COVER is complete under
E-reductions for the class MIN F
3 MAX SNP Closure and APX-PB
In this section, we will establish the following theorem and examine its implications. The proof is based on
the results of Arora et al [3] on efficient proof verifications.
Theorem 1 MAX
Remark 5 The seeming weakness that MAX SNP only captures polynomially bounded APX problems
can be removed by using looser forms of approximation-preserving reduction in defining the closure. In
particular, Crescenzi and Trevisan [8] define the notion of a PTAS-preserving reduction under which
APX-PB. Using their result in conjunction with the above theorem, it is easily seen that MAX
This weaker reduction is necessary to allow for reductions from fine-grained optimization problems to
coarser (polynomially-bounded) optimization problems (cf. [8]).
The following is a surprising consequence of Theorem 1.
Theorem 2 MAX
Papadimitriou and Yannakakis [22] (implicitly) introduced both these closure classes but did not conjecture
them to be the same. It would be interesting to see if this equality can be shown independent of the
result of Arora et al [3]. We also obtain the following resolution to the problem posed by Papadimitriou and
Yannakakis [22] of finding complete problems for MAX NP.
Theorem 3 MAX SAT is complete for MAX NP.
The following sub-sections establish that MAX SNP ' APX-PB. The idea is to first E-reduce any minimization
problem in APX-PB to a maximization problem in therein, and then E-reduce any maximization
problem in APX-PB to a specific complete problem for MAX SNP, viz., MAX 3-SAT.
Since an E-reduction forces the optimas of the two problems involved to be related by polynomial
factors, it is easy to see that MAX SNP ' APX-PB. Combining, we establish Theorem 1.
3.1 Reducing Minimization to Maximization
Observe that the fact that P belongs to APX implies the existence of an approximation algorithm A and a
constant c such that
c
Henceforth, we will use a(I) to denote V (I; A(I)). We first reduce any minimization problem P 2 APX-PB
to a maximization problem P 0 2 APX-PB, where the latter is obtained by merely modifying the objective
function for P, as follows: let P 0 have the objective function V 0 (I;
instances I and solutions S for P. It can be verified that the optimum value for any instance I of P 0 always
lies between a(I) and (c 1)a(I). Thus, A is a 1)-approximation algorithm for P 0 . If S is a ffi -error
solution to the optimum of P 0 , i.e.,
where OPT 0 (I) is the optimal value of V 0 for I. We obtain that
c
c
c
Thus a solution s to P 0 with error ffi is a solution to P with error at most (c implying an E-reduction
with
3.2 NP Languages and MAX 3-SAT
The following theorem, adapted from a result of Arora, Lund, Motwani, Sudan, and Vazirani [3], is critical
to our E-reduction of maximization problems to MAX 3-SAT.
Theorem 4 Given a language L 2 NP and an instance x 2 S n , one can compute in polynomial time an
instance F x of MAX 3-SAT, with the following properties.
1. The formula F x has m clauses, where m depends only on n.
2. There exists a constant ffl ? 0 such that (1 \Gamma ffl)m clauses of F x are satisfied by some truth assignment.
3. If x 2 L, then F x is (completely) satisfiable.
4. If x 62 L, then no truth assignment satisfies more than clauses of F x .
5. Given a truth assignment which satisfies more than clauses of F x , a truth assignment which
satisfies F x completely can be constructed in polynomial time.
Some of the properties above may not be immediately obvious from the construction given by Arora,
Lund, Motwani, Sudan, and Szegedy [3]. It is easy to verify that they provide a reduction with properties
(1), (3) and (4). Property (5) is obtained from the fact that all assignments which satisfy most clauses are
actually close (in terms of Hamming distance) to valid codewords from a linear code, and the uniquely
error-corrected codeword obtained from this "corrupted code-word" will satisfy all the clauses of F x .
Property (2) requires a bit more care and we provide a brief sketch of how it may be ensured. The idea
is to revert back to the PCP model and redefine the proof verification game. Suppose that the original game
had the properties that for x 2 L there exists a proof such that the verifier accepts with probability 1, and
otherwise, for x 62 L, the verifier accepts with probability at most 1=2. We now augment this game by
adding to the proof a 0th bit which the prover uses as follows: if the bit is set to 1, then the prover "chooses"
to play the old game, else he is effectively "giving up" on the game. The verifier in turn first looks at the 0th
bit of the proof. If this is set, then she performs the usual verification, else she tosses an unbiased coin and
accepts if and only if it turns up heads. It is clear that for x 2 L there exists a proof on which the verifier
always accepts. Also, for x 62 L no proof can cause the verifier to accept with probability greater than 1=2.
Finally, by setting the 0th bit to 0, the prover can create a proof which the verifier accepts with probability
exactly 1=2. This proof system can now be transformed into a 3-CNF formula of the desired form.
3.3 Reducing Maximization to MAX 3-SAT
We have already established that, without loss of generality, we only need to worry about maximization
problems Consider such a problem P, and let A be a polynomial-time algorithm which
delivers a c-approximation for P, where c is some constant. Given any instance I of P, let
the bound on the optimum value for I obtained by running A on input I. Note that this may be a stronger
bound than the a priori polynomial bound on the optimum value for any instance of length jIj. An important
consequence is that p - c OPT (I).
We generate a sequence of NP decision problems L Given an
instance I, we create p formulas F i , for using the reduction from Theorem 4, where ith formula
is obtained from the NP language L i .
Consider now the formula
that has the following features.
ffl The number of satisfiable clauses of F is exactly
where ffl and m are as guaranteed by Theorem 4.
ffl Given an assignment which satisfies (1 clauses of F , we can construct in polynomial
time a solution to I of value at least j. To see this, observe the following: any assignment which
so many clauses must satisfy more than clauses in at least j of the formulas F i . Let i be
the largest index for which this happens; clearly, i - j. Furthermore, by property (5) of Theorem 4,
we can now construct a truth assignment which satisfies F i completely. This truth assignment can be
used to obtain a solution S such that V (I;
In order to complete the proof it remains to be shown that given any truth assignment with error ffi , i.e.,
which satisfies MAX =(1 clauses of F , we can find a solution S for I with error E(I;
some constant fi. We show that this is possible for cffl)=ffl. The main idea behind finding such a
solution is to use the second property above to find a "good" solution to I using a "good" truth assignment
for F .
Suppose we are given a solution which satisfies MAX =(1 clauses. Since MAX =(1
we can use the second feature from above to
construct a solution S 1 such that
fflm
c
readily seen that
Assuming we obtain that
On the other hand, if then the error in a solution S 2 obtained by running the c-approximation
algorithm for P is given by
Therefore, choosing immediately obtain that the solution with larger value, among S 1
has error at most fi ffi . Thus, this reduction is indeed an E-reduction.
4 Generic Reductions and an Approximation Hierarchy
In this section we describe a generic technique for turning a hardness result into an approximation preserving
reduction.
We start by listing the kind of constraints imposed on the hardness reduction, the approximation class
and the optimization problem. We will observe at the end that these restrictions are obeyed by all known
hardness results and the corresponding approximation classes.
Definition 11 (Additive Problems) An NPO problem P is said to be additive if there exists an operator
which maps a pair of instances I 1 and I 2 to an instance I 1 I 2 such that OPT
Definition 12 (Downward Closed Family) A family of functions is said to be
downward closed if for all g 2 F and for all constants c, g 0 (n) 2 O(g(n c )) implies that g 0 2 F . A function
g is said to be hard for the family F if for all g 0 2 F , there exists a constant c such that g 0 (n) 2 O(g(n c ));
the function g is said to be complete for F if g is hard for F and g 2 F .
For a downward closed family F , the class F -APX consists of all problems
approximable to within a ratio of g(jIj) for some function g 2 F .
Definition 14 (Canonical Hardness) An NP maximization problem P is said to be canonically hard for the
class F -APX if there exists a transformation T , constants n 0 and c, and a gap function G which is hard for
the family F , such that given an instance x of 3-SAT on n - n 0 variables and N - n c , I = T (x; N) is an
instance of P with the following properties.
ffl If x 2 3-SAT, then OPT
ffl If x 62 3-SAT, then OPT
ffl Given a solution S to I with V (I; S) ? N=G(N), a truth assignment satisfying x can be found in
polynomial time.
Canonical hardness for NP minimization problems is analogously defined: OPT when the
formula is satisfiable and OPT Given any solution with value less than NG(N),
one can construct a satisfying assignment in polynomial time.
4.1 The Reduction
Theorem 5 If F is a downward closed family of functions, and an additive NPO problem W is canonically
hard for the class F -APX, then all problems in F -APX E-reduce to P.
Proof: Let P be a problem in F-APX, approximable to within c(:), and let W be a problem shown to
be hard to within a factor G(:) where G is complete for F . We start with the special case where both P
and W are maximization problems. We describe the functions f , g and the constant fi as required for an
E-reduction.
Let I 2 P be an instance of size n; pick N so that c(n) is O(G(N)). To describe our reduction, we
need to specify the functions f and g. The function f is defined as follows. Let
each denote the NP-language fIj OPT (I) - ig. Now for each i, we create an
instance OE i 2 W of size N such that if I 2 L i then OPT (OE i ) is N , and it is N=G(N) otherwise. We define
We now construct the function g. Given an instance I 2 P and a solution s 0 to f(I), we compute a
solution s to I in the following manner. We first use A to find a solution s 1 . We also compute a second
solution s 2 to I as follows. Let j be the largest index such that the solution s 0 projects down to a solution s
to the instance OE j such that V 0
This in turn implies we can find a solution s 2 to witness
Our solution s is the one among s 1 and s 2 that yields the larger objective function value.
We now show that the reduction holds for
c(n)
Consider the following two cases:
Case 1 [j - m]: In this case, V (I; m. Thus s is an (ff \Gamma 1) approximate solution to I. We now
argue that s 0 is at best a (ff \Gamma 1)=fi approximate solution to OE. We start with the following upper bound on
c(n)
G(N) \GammaG(N)
Thus the approximation factor achieved by s 0 is given by
Nm
So in this case s 1 (and hence s) approximates I to within a factor of fi ffl, if s 0 approximates OE to within a
factor of ffl.
Case 2 [j - m]: Let flm. Note that fl ? 1 and that s is an (ff \Gamma fl)=fl approximate solution to I. We
bound the value of the solution s 0 to OE as
c(n)
and its quality as
Thus in this case also we find that s (by virtue of s 2 ) is a solution of quality fi ffl if s 0 is a solution of quality s.
We now consider the more general cases where P and W are not both maximization problems. For the
case where both are minimization problems, the above transformation works with one minor change. When
creating OE i , the NP language consists of instances (I; i) such that there exists s with
For the case where P is a minimization problem and W is a maximization problem, we first E-reduce P
to a maximization problem P 0 and then proceed as before. The reduction proceeds as follows. The objective
function of P 0 is defined as V 0 (I; To begin with, it is easy to verify that P 2 F-APX
implies
Let s be a fi approximate solution to instance I of P. We will show that s is at best a fi=2 approximate
solution to instance I of P 0 . Assume, without loss of generality, that fi 6= 0. Then
Multiplying by 2m 2 =(OPT (I)V (I; s)), we get
2:
This implies that
Upon rearranging,
Thus the reduction from P to P 0 is an E-reduction.
Finally, the last remaining case, i.e., P being a maximization problem and W being a minimization
problem, is dealt with similarly: we transform P into a minimization problem P 0 .
Remark 6 This theorem appears to merge two different notions of the relative ease of approximation of
optimization problems. One such notion would consider a problem P 1 easier than P 2 if there exists an
approximation preserving reduction from P 1 to P 2 . A different notion would regard P 1 to be easier than
one seems to have a better factor of approximation than the other. The above statement essentially
states that these two comparisons are indeed the same. For instance, the MAX CLIQUE problem and the
CHROMATIC NUMBER problem, which are both in poly-APX, are inter-reducible to each other. The
above observation motivates the search for other interesting function classes f , for which the class f -APX
may contain interesting optimization problems.
4.2 Applications
The following is a consequence ofTheorem 5.
Theorem 6
a)
b) If SET COVER is canonically hard to approximate to within a factor of W(log n), then
We briefly sketch the proof of this theorem. The hardness reduction for MAX SAT and CLIQUE
are canonical [3, 11]. The classes APX-PB, poly-APX, log-APX are expressible as classes F-APX for
downward closed function families. The problems MAX SAT, MAX CLIQUE and SET COVER are
additive. Thus, we can now apply Theorem 5.
Remark 7 We would like to point out that almost all known instances of hardness results seem to be shown
for problems which are additive. In particular, this is true for all MAX SNP problems, MAX CLIQUE,
CHROMATIC NUMBER, and SET COVER. One case where a hardness result does not seem to directly
apply to an additive problem is that of LONGEST PATH [17]. However in this case, the closely related
LONGEST S-T PATH problem is easily seen to be additive and the hardness result essentially stems from
this problem. Lastly, the most interesting optimization problems which do not seem to be additive are
problems related to GRAPH BISECTION or PARTITION, and these also happen to be notable instances
where no hardness of approximation results have been achieved!
5 Local Search and MAX SNP
In this section we present a formal definition of the paradigm of non-oblivious local search, and describe
how it applies to a generic MAX SNP problem. Given a MAX SNP problem P, recall that the goal is to
find a structure S which maximizes the objective function: V (I;
~x F(I; S; ~x). In the subsequent
discussion, we view S as a k-dimensional boolean vector.
5.1 Classical Local Search
We start by reviewing the standard mechanism for constructing a local search algorithm. A ffi-local algorithm
A for P is based on a distance function D(S 1 which is the Hamming distance between two k-dimensional
vectors. The ffi-neighborhood of a structure S is given by N(S;
U is the universe. A structure S is called ffi-optimal if 8S
algorithm computes a ffi-optimum by performing a series of greedy improvements to an initial structure S 0 ,
where each iteration moves from the current structure S i to some S
For constant ffi , a ffi-local search algorithm for a polynomially-bounded NPO problem runs in polynomial
time because:
ffl each local change is polynomially computable, and
ffl the number of iterations is polynomially bounded since the value of the objective function improves
monotonically by an integral amount with each iteration, and the optimum is polynomially-bounded.
5.2 Non-Oblivious Local Search
A non-oblivious local search algorithm is based on a 3-tuple hS is the initial solution
structure which must be independent of the input, F(I; S) is a real-valued function referred to as the weight
function, and D is a real-valued distance function which returns the distance between two structures in some
appropriately chosen metric. The distance function D is computable in time polynomial in jU j. Thus as
before, for constant ffi, a non-oblivious ffi -local algorithm terminates in time polynomial in the input size.
The classical local search paradigm, which we call oblivious local search, makes the natural choice for
the function F(I; S), and the distance function D, i.e., it chooses them to be V (I; S) and the Hamming
distance. However, as we show later, this choice does not always yield a good approximation ratio. We
now formalize our notion of this more general type of local search.
Definition 15 (Non-Oblivious Local Search Algorithm) A non-oblivious local search algorithm is a
local search algorithm whose weight function is defined to be
~x
r
where r is a constant, F i 's are quantifier-free first-order formulas, and the profits p i are real constants. The
distance function D is an arbitrary polynomial-time computable function.
A non-oblivious local search can be implemented in polynomial time in much the same way as oblivious
local search. Note that the we are only considering polynomially-bounded weight functions and the profits
are fixed independent of the input size. In general, the non-oblivious weight functions do not direct the
search in the direction of the actual objective function. In fact, as we will see, this is exactly the reason why
they are more powerful and allow for better approximations.
Definition (Non-Oblivious GLO) The class of problems NON-OBLIVIOUS GLO consists of all problems
which can be approximated within constant factors by a non-oblivious ffi -local search algorithm for some
constant ffi .
Remark 8 We make some observations about the above definition. It would be perfectly reasonable to
allow weight functions which are non-linear, but we stay with the above definition for the purposes of this
paper. Allowing only a constant number of predicates in the weight functions enables us to prevent the
encoding of arbitrarily complicated approximation algorithms. The structure S is a k-dimensional vector,
and so a convenient metric for the distance function D is the Hamming distance. This should be assumed
to be the underlying metric unless otherwise specified. However, we have found that it is sometimes useful
to modify this, for example by modifying the Hamming distance so that the complement of a vector is
considered to be at distance 1 from it. Finally, it is sometimes convenient to assume that the local search
makes the best possible move in the bounded neighborhood, rather than an arbitrary move which improves
the weight function. We believe that this does not increase the power of non-oblivious local search.
6 The Power of Non-Oblivious Local Search
We will show that there exists a choice of a non-oblivious weight function for MAX k-SAT such that any
assignment which is 1-optimal with respect to this weight function, yields a performance ratio of 2 k
with respect to the optimal. But first, we obtain tight bounds on the performance of oblivious local search
for MAX 2-SAT, establishing that its performance is significantly weaker than the best-known result even
when allowed to search exponentially large neighborhoods. We use the following notation: for any fixed
truth assignment ~
is the set of clauses in which exactly i literals are true; and, for a set of clauses S,
W (S) denotes the total weight of the clauses in S.
6.1 Oblivious Local Search for MAX 2-SAT
We show a strong separation in the performance of oblivious and non-oblivious local search for MAX 2-SAT.
Suppose we use a ffi-local strategy with the weight function F being the total weight of the clauses satisfied
by the assignment, i.e., The following theorem shows that for any an
oblivious ffi -local strategy cannot deliver a performance ratio better than 3=2. This is rather surprising given
that we are willing to allow near-exponential time for the oblivious algorithm.
Theorem 7 The asymptotic performance ratio for an oblivious ffi -local search algorithm for MAX 2-SAT
is 3=2 for any positive This ratio is still bounded by 5=4 when ffi may take any value less than
n=2.
Proof: We show the existence of an input instance for MAX 2-SAT which may elicit a relatively poor
performance ratio for any ffi -local algorithm provided In our construction of such an input instance,
we assume that n - 2ffi + 1. The input instance comprises of a disjoint union of four sets of clauses, say
defined as below:
1-i!j-n
1-i!j-n
2ffi+2-i-n
i!j-n
Clearly,
1). Without loss of generality, assume
that the current input assignment is ~
1). This satisfies all clauses in G 1 and G 2 . But none of
the clauses in G 3 and G 4 are satisfied. If we flip the assignment of values to any k - ffi variables, it would
unsatisfy precisely k(n \Gamma clauses in G 1 . This is the number of clauses in G 1 flipped
variable occurs with an unflipped variable.
On the other hand, flipping the assigned values of any k - ffi variables can satisfy at most k(n \Gamma
clauses in G 3 as we next show.
denote the set of clauses on n variables given by
We claim the following.
assignment of values to the n variables such that at most k - ffi variables have been assigned
value false, can satisfy at most k(n \Gamma clauses in P(n; ffi).
Proof: We prove by simultaneous induction on n and ffi that the statement is true for any instance
P(n; ffi) where n and ffi are non-negative integers such that n. The base case includes
and is trivially verified to be true for the only allowable value of ffi , namely We now assume
that the statement is true for any instance P(n Consider now the
instance P(n; ffi ). The statement is trivially true for
g be any choice of k - ffi variables such that q. Again the assertion is
trivially true if We assume that k - 2 from now on. If we delete all clauses containing the
variables z 1 and z 2 from P(n; ffi ), we get the instance P(n \Gamma 2; 1). We now consider three cases.
Case 1 In this case, we are reduced to the problem of finding an upper bound on the maximum
number of clauses satisfied by setting any k variables to false in P(n \Gamma 2; use
the inductive hypothesis to conclude that no more than (n clauses will be satisfied. Thus the
assertion holds in this case. However, we may not directly use the inductive hypothesis if But in this
case we observe that since by the inductive hypothesis, setting any k \Gamma 1 variables in P(n \Gamma 2;
false, satisfies at most (n clauses, assigning the value false to any set of k variables,
can satisfy at most
clauses. Hence the assertion holds in this case also.
Case In this case, z j 1
satisfies one clause and the remaining variables satisfy at most
clauses by the inductive hypothesis on Adding up the two terms,
we see that the assertion holds.
Case 3 We analyze this case based on whether
precisely clauses and the remaining variables, satisfy at most (n
clauses using the inductive hypothesis. Thus the assertion still holds. Otherwise, z 1 satisfies precisely
clauses and the remaining no more than (n clauses using the
inductive hypothesis. Summing up the two terms, we get (n \Gamma k)k as the upper bound on the total number
of clauses satisfied. Thus the assertion holds in this case also.
To see that this bound is tight, simply consider the situation when the k variables set to false are
ffi. The total number of clauses satisfied is given by
Assuming that each clause has the same weight, Lemma 1 allows us to conclude that a ffi-local algorithm
cannot increase the total weight of satisfied clauses with this starting assignment. An optimal assignment on
the other hand can satisfy all the clauses by choosing the vector ~
0). Thus the performance
ratio of a ffi-local algorithm, say R ffi , is bounded as
For any asymptotically converges to 3=2. We next show that this bound is tight
since a 1-local algorithm achieves it. However, before we do so, we make another intriguing observation,
namely, for any ffi ! n=2, the ratio R ffi is bounded by 5=4.
To see that a 1-local algorithm ensures a performance ratio of 3=2, consider any 1-optimal assignment
~
Z and let ff i denote the set of clauses containing the variable z i such that no literal in any clause of ff i is
satisfied by ~
Z . Similarly, let fi i denote the set of clauses containing the variable z i such that precisely one
literal is satisfied in any clause in fi i and furthermore, it is precisely the literal containing the variable z i . If
we complement the value assigned to the variable z i , it is exactly the set of clauses in ff i which becomes
satisfied and the set of clauses in fi i which is no longer satisfied. Since ~
Z is 1-optimal, it must be the
case that W (ff i ) - W (fi i ). If we sum up this inequality over all the variables, then we get the inequality
We observe that
because each clause in S 0 gets counted twice while each clause in S 1 gets counted exactly once. Thus the
fractional weight of the number of clauses not satisfied by a 1-local assignment is bounded as
Hence the performance ratio achieved by a 1-local algorithm is bounded from above by 3=2. Combining
this with the upper bound derived earlier, we conclude that R We may summarize our results as
follows.
Lemma 2 The performance ratio R ffi for any ffi -local algorithm for MAX 2-SAT using the weight function
positive integer o(n). Furthermore, this ratio is still bounded by
5=4 when ffi may take any value less than n=2.
6.2 Oblivious Local Search for MAX 2-SAT
We now illustrate the power of non-oblivious local search by showing that it achieves a performance ratio
of 4=3 for MAX 2-SAT, using 1-local search with a simple non-oblivious weight function.
Theorem 8 Non-oblivious 1-local search achieves a performance ratio of 4=3 for MAX 2-SAT.
Proof: We use the non-oblivious weight function
Consider any assignment ~
Z which is 1-optimal with respect to this weight function. Without loss of
generality, we assume that the variables have been renamed such that each unnegated literal gets assigned
the value true. Let P i;j and N i;j respectively denote the total weight of clauses in S i containing the literals
z j and z j , respectively. Since ~
Z is a 1-optimal assignment, each variable z j must satisfy the following
equation.
\Gamma2 P 2;j \Gamma2 P 1;j +2 N 1;j +2 N 0;j - 0:
Summing this inequality over all the variables, and using
we obtain the following inequality:
This immediately implies that the total weight of the unsatisfied clauses at this local optimum is no more
than 1=4 times the total weight of all the clauses. Thus, this algorithm ensures a performance ratio of 4=3.
Remark 9 The same result can be achieved by using the oblivious weight function, and instead modifying
the distance function so that it corresponds to distances in a hypercube augmented by edges between nodes
whose addresses are complement of each other.
6.3 Generalization to MAX k-SAT
We can also design a non-oblivious weight function for MAX k-SAT such that a 1-local strategy ensures a
performance ratio of 2 k 1). The weight function F will be of the form
the coefficients c i 's will be specified later.
Theorem 9 Non-oblivious 1-local search achieves a performance ratio of 2 k
Proof: Again, without loss of generality, we will assume that the variables have been renamed so that
each unnegated literal is assigned true under the current truth assignment. Thus the set S i is the set of
clauses with i unnegated literals.
denote the change in the current weight when we flip the value of z j , that
is, set it to 0. It is easy to verify the following equation:
(D
Thus when the algorithm terminates, we know that @F
Summing over all values of
j, and using the fact
get the following inequality.
We now determine the values of D i 's such that the coefficient of each term on the left hand side is unity.
It can be verified that
achieves this goal. Thus the coefficient of W (S 0 ) on the right hand side of equation (2) is
the weight of the clauses not satisfied is bounded by 1=2 k times the total weight of all the clauses. It is
worthwhile to note that this is regardless of the value chosen for the coefficient c 0 .
7 Local Search for CSP and MAX SNP
We now introduce a class of constraint satisfaction problems such that the problems in MAX SNP are exactly
equivalent to the problems in this class. Furthermore, every problem in this class can be approximated to
within a constant factor by a non-oblivious local search algorithm.
7.1 Constraint Satisfaction Problems
The connection between the syntactic description of optimization problems and their approximability through
non-oblivious local search is made via a problem called MAX k-CSP which captures all the problems in
MAX SNP as a special case.
Definition 17 (k-ary Constraint) Let be a set of boolean variables. A k-ary constraint
on Z is is a size k subset of Z, and is a k-ary boolean
predicate.
Definition Given a collection C of weighted k-ary constraints over the variables
g, the MAX k-CSP problem is to find a truth assignment satisfying a maximum weight
sub-collection of the constraints.
The following theorem shows that MAX k-CSP problem is a "universal" MAX SNP problem, in that it
contains as special cases all problems in MAX SNP.
Theorem
a) For fixed k, MAX k-CSP 2 MAX SNP.
Moreover, the k-CSP instance
corresponding to any instance of this problem can be computed in polynomial time.
7.2 Non-Oblivious Local Search for MAX k-CSP
A suitable generalization of the non-oblivious local search algorithm for MAX k-SAT yields the following
result.
Theorem 11 A non-oblivious 1-local search algorithm has performance ratio 2 k for MAX k-CSP.
Proof: We use an approach similar to the one used in the previous section to design a non-oblivious
weight function F for the weighted version of the MAX k-CSP problem such that a 1-local algorithm yields
performance ratio to this problem.
We consider only the constraints with at least one satisfying assignment. Each such constraint can be
replaced by a monomial which is the conjunction of some k literals such that when the monomial evaluates to
true the corresponding literal assignment represents a satisfying assignment for the constraint. Furthermore,
each such monomial has precisely one satisfying assignment. We assign to each monomial the weight of
the constraint it represents. Thus any assignment of variables which satisfies monomials of total weight W 0 ,
also satisfies constraints in the original problem of total weight W 0 .
denote the monomials with i true literals, and assume that the weight function F is of the form
assuming that the variables have been renamed so that the current assignment gives
value true to each variable, we know that for any variable z j , @F
is given by equation (1). As before, using
the fact that for any 1-optimal assignment, @F
summing over all values of j, we
can write the following inequality.
We now determine the values of D i 's such that the coefficient of each term on the left hand side is unity. It
can be verified that
achieves this goal. Thus the coefficient of W (S k ) on the right hand side of equation (1) is
the total weight of clauses satisfied is at least 1=2 k times the total weight of all the clauses with at least one
satisfiable assignment.
We conclude the following theorem.
Theorem 12 Every optimization problem P 2 MAX SNP can be approximated to within some constant
factor by a (uniform) non-oblivious 1-local search algorithm, i.e.,
For a problem expressible as k-CSP, the performance ratio is at most 2 k .
8 Non-Oblivious versus Oblivious GLO
In this section, we show that there exist problems for which no constant factor approximation can be obtained
by any ffi -local search algorithm with oblivious weight function, even when we allow ffi to grow with the
input size. However, a simple 1-local search algorithm using an appropriate non-oblivious weight function
can ensure a constant performance ratio.
8.1 MAX 2-CSP
The first problem is an instance of MAX 2-CSP where we are given a collection of monomials such that
each monomial is an "and" of precisely two literals. The objective is to find an assignment to maximize the
number of monomials satisfied.
We show an instance of this problem such that for every there exists an instance one of whose
local optima has value that is a vanishingly small fraction of the global optimum.
The input instance consists of a disjoint union of two sets of monomials, say G 1 and G 2 , defined as
below:
1-i!j-n
i!j-n
Clearly,
. Consider the truth assignment ~
1). It satisfies
all monomials in G 2 but none of the monomials in G 1 . We claim that this assignment is ffi -optimal with
respect to the oblivious weight function. To see this, observe that complementing the value of any p - ffi
variables will unsatisfy at least ffip=2 monomials in G 2 for any On the other hand, this will satisfy
precisely
. For any p - ffi , we have (ffip)=2 -
so Z is a ffi -local optimum.
The optimal assignment on the other hand, namely ~
all monomials in G 1 .
Thus, for n=2, the performance ratio achieved by any ffi -local algorithm is no more than
which asymptotically diverges to infinity for any We have already seen in Section 7 that a 1-
local non-oblivious algorithm ensures a performance ratio of 4 for this problem. Since this problem is in
MAX SNP, we obtain the following theorem.
Theorem 13 There exist problems in MAX SNP such that for oblivious algorithm can
approximate them to within a constant performance ratio, i.e.,
MAX SNP 6' GLO:
8.2 Vertex Cover
Ausiello and Protasi [4] have shown that VERTEX COVER does not belong to the class GLO and, hence,
there does not exist any constant ffi such that an oblivious ffi-local search algorithm can compute a constant
factor approximation. In fact, their example can be used to show that for any the performance
ratio ensured by ffi-local search asymptotically diverges to infinity. However, we show that there exists a
rather simple non-oblivious weight function which ensures a factor 2 approximation via a 1-local search. In
fact, the algorithm simply enforces the behavior of the standard approximation algorithm which iteratively
builds a vertex cover by simply including both end-points of any currently uncovered edge.
We assume that the input graph G is given as a structure (V; fEg) where V is the set of vertices and
encodes the edges of the graph. Our solution is represented by a 2-ary predicate M which
is iteratively constructed so as to represent a maximal matching. Clearly, the end-points of any maximal
matching constitute a valid vertex cover and such a vertex cover can be at most twice as large as any other
vertex cover in the graph. Thus M is an encoding of the vertex cover computed by the algorithm.
The algorithm starts with M initialized to the empty relation and at each iteration, at most one new pair
is included in it. The non-oblivious weight function used is as below:
where
Let M encode a valid matching in the graph G. 2 We make the following observations.
obtained from M by either deleting an edge from it, or including an edge in which
is incident on an edge of M , has the property that F(I; M 0 ) - F(I; M). Thus in a 1-local search
from M , we will never move to a relation M 0 which does not encode a valid matching of G.
ffl On the other hand, if a relation M 0 corresponds to the encoding of a matching in G which is larger
than the matching encoded by M , then F(I; does not encode a maximal
matching in G, there always exist a relation in its 1-neighborhood of larger weight than itself.
These two observations, combined with the fact that we start with a valid initial matching (the empty
matching), immediately allow us to conclude that any 1-optimal relation M always encodes a maximal
matching in G. We have established the following.
Theorem 14 A 1-local search algorithm using the above non-oblivious weight function achieves a performance
ratio of 2 for the VERTEX COVER problem.
Theorem 15 GLO is a strict subset of NON-OBLIVIOUS GLO:
2 It is implicit in our formulation that M will correspond to a lower triangular matrix representation of the matching edges.
9 The Traveling Salesman Problem
The TSP(1,2) problem is the traveling salesman problem restricted to complete graphs where all edge
weights are either 1 or 2; clearly, this satisfies the triangle inequality. Papadimitriou and Yannakakis [23]
showed that this problem is hard for MAX SNP. The natural weight function for TSP(1,2), that is, the weight
of the tour, can be used to show that a 4-local algorithm yields a 3=2 performance ratio. The algorithm starts
with an arbitrary tour and in each iteration, it checks if there exist two disjoint edges (a; b) and (c; d) on the
tour such that deleting them and replacing them with the edges (a; c) and (b; d) yields a tour of lesser cost.
Theorem 4-local search algorithm using the oblivious weight function achieves a 3=2 performance
ratio for TSP(1,2).
Proof: Let C be a 4-optimal solution and let Let - be a permutation such that the vertices in C occur in
the order v - Consider any optimal solution O. With each unit cost edge e in O, we associate
a unit cost edge e 0 in C as follows. Let
consider the edges e
) on C. We claim either e 1 or e 2 must be of unit
cost. Suppose not, then the tour C 0 which is obtained by simply deleting both e 1 and e 2 and inserting the
edges e and
has cost at least one less than C. But C is 4-optimal and thus this is a
contradiction.
Let UO denotes the set of unit cost edges in O and let UC be the set of unit cost edges in C which form
the image of UO under the above mapping. Since an edge e
in UC can only be the image of
unit cost edges incident on v - i
in O and since O is a tour, there are at most two edges in UO which map to
e 0 . Thus jU C j - jU O j=2 and hence
cost(O)
The above bound can be shown to be tight.
Theorem 17 There exists a TSP(1,2) instance such that the optimal solution has cost n + O(1) and there
exists a certain 4-optimal solution for it with cost 3n=2 +O(1).
Maximum Independent Sets in Bounded Degree Graphs
The input instance to the maximum independent set problem in bounded degree graphs, denoted MIS-B, is
a graph G such that the degree of any vertex in G is bounded by a constant D. We present an algorithm with
performance ratio (
1)=2 for this problem when D - 10.
Our algorithm uses two local search algorithms such that the larger of the two independent sets computed
by these algorithms, gives us the above claimed performance ratio. We refer to these two algorithms as A 1
and A 2 .
In our framework, the algorithm A 1 can be characterized as a 3-local algorithm with the weight function
simply being jI Thus if we start with I initialized to empty set, it is easy to see that at
each iteration, I will correspond to an independent set in G. A convenient way of looking at this algorithm
is as follows. We define an swap to be the process of deleting i vertices from S and including j
vertices from the set V \Gamma S to the set S. In each iteration, the algorithm A 1 performs either a 0
however, can be interpreted as j applications of 0
swaps. Thus the algorithm may be viewed as executing a 0 swap at each iteration.
The algorithm terminates when neither of these two operations is applicable.
Let I denote the 3-optimal independent set produced by the algorithm A 1 . Furthermore, let O be any
optimal independent set and let We make the following useful observations.
ffl Since for no vertex in I , a 0 can be performed, it implies that each vertex in V \Gamma I must
have at least one incoming edge to I .
ffl Similarly, since no 1 swaps can be performed, it implies that at most jI \Gamma X j vertices in O \Gamma I
can have precisely one edge coming into I . Thus vertices in O \Gamma X
must have at least two edges entering the set I .
A rather straightforward consequence of these two observations is the following lemma.
Lemma 3 The algorithm A 1 has performance ratio (D + 1)=2 for MIS-B.
Proof: The above two observations imply that the minimum number of edges entering I from the
vertices in O \Gamma X is On the other hand, the maximum number of edges coming out
of the vertices in I to the vertices in O \Gamma X is bounded by jI \Gamma X jD. Thus we must have
Rearranging, we get
which yields the desired result.
This nearly matches the approximation ratio of D=2 due to Hochbaum [15]. It should be noted that the
above result holds for a broader class of graphs, viz., k-claw free graphs. A graph is called
there does not exist an independent set of size k or larger such that all the vertices in the independent set are
adjacent to the same vertex. Lemma 3 applies to (D
Our next objective is to further improve this ratio by using the algorithm A 1 in combination with the
algorithm A 2 . The following lemma uses a slightly different counting argument to give an alternative bound
on the approximation ratio of the algorithm A 1 when there is a constraint on the size of the optimal solution.
Lemma 4 For any real number c ! D, the algorithm A 1 has performance ratio (D \Gamma c)=2 for MIS-B when
the optimal value itself is no more than
Proof: As noted earlier, each vertex in V \Gamma I must have at least one edge coming into the set I and at
least vertices in O must have at least two edges coming into I . Therefore, the following inequality
must be satisfied:
Thus Finally, observe that
The above lemma shows that the algorithm A 1 yields a better approximation ratio when the size of the
optimal independent set is relatively small.
The algorithm A 2 is simply the classical greedy algorithm. This algorithm can be conveniently included
in our framework if we use directed local search. If we let N(I) denote the set of neighbors of the vertices
in I , then the weight function is simply jI j(D 1). It is not
difficult to see that starting with an empty independent set, a 1-local algorithm with directed search on above
weight function simply simulates a greedy algorithm. The greedy algorithm exploits the situation when
the optimal independent set is relatively large in size. It does so by using the fact that the existence of a
large independent set in G ensures a large subset of vertices in G with relatively small average degree. The
following two lemmas characterize the performance of the greedy algorithm.
Lemma 5 Suppose there exists an independent set X ' V such that the average degree of vertices in X
is bounded by ff. Then for any ff - 1, the greedy algorithm produces an independent set of size at least
Proof: The greedy algorithm iteratively chooses a vertex of smallest degree in the remaining graph
and then deletes this vertex and all its neighbors from the graph. We examine the behavior of the greedy
by considering two types of iterations. First consider the iterations in which it picks a vertex outside X .
Suppose in the ith such iteration, it picks a vertex in exactly k i neighbors in the set X in the
remaining graph. Since each one of these k i vertices must also have at least k i edges incident on them,
we loose at least k 2
edges incident on X . Suppose only p such iterations occur and let
observe that
Secondly, we consider the iterations when the greedy selects a vertex in X .
Then we do not loose any other vertices in X because X is an independent set. Thus the total size of the
independent set constructed by the greedy algorithm is at least p
By the Cauchy-Schwartz inequality,
Therefore, we have (1
Rearranging, we obtain that
Thus
and the result follows.
Lemma 6 For non-negative real number c - 3D \Gamma
has performance ratio (D \Gamma c)=2 for MIS-B when the optimal value itself is at least ((D \Gamma c)jV j)=(D+c+4).
Proof: Observe that the average degree of vertices in O is bounded by (jV \Gamma OjD=jOj) and thus using
the fact that jOj - (D \Gamma c)jV we know that the algorithm A 2 computes an independent set of
size at least jOj=(1 Hence it is sufficient to
determine the range of values c can take such that the following inequality is satisfied:
Substituting the bound on the value of ff and rearranging the terms of the equation, yields the following
Since c must be strictly bounded by D, the above quadratic equation is satisfied for any choice of
Combining the results of Lemmas 4 and 6 and choosing the largest allowable value for c, we get the
following result.
Theorem approximation algorithm which simply outputs the larger of the two independent sets
computed by the algorithms A 1 and A 2 , has performance ratio (
The performance ratio claimed above is essentially D=2:414. This improves upon the long-standing
approximation ratio of D=2 due to Hochbaum [15], when D - 10. However, very recently, there has been
a flurry of new results for this problem. Berman and Furer [6] have given an algorithm with performance
(D when D is even, and (D fixed constant.
Halldorsson and Radhakrishnan [14] have shown that algorithm A 1 when run on k-clique free graphs, yields
an independent set of size at least 2n=(D They combine this algorithm with a clique-removal based
scheme to achieve a performance ratio of D=6(1

Acknowledgements

Many thanks to Phokion Kolaitis for his helpful comments and suggestions. Thanks also to Giorgio Ausiello
and Pierluigi Crescenzi for guiding us through the intricacies of approximation preserving reductions and
the available literature on it.



--R

New Local Search Approximation Techniques for Maximum Generalized Satisfiability Problems.
Approximate Solution of NP Optimization Problems.
Proof Verification and Hardness of Approximation Problems.
Optimization Problems and Local Optima.
Efficient probabilistically checkable proofs.
Approximating Maximum Independent Set in Bounded Degree Graphs.
Introduction to the Theory of Complexity.

Completeness in approximation classes.
Generalized First-Order Spectra and Polynomial-time Recognizable Sets

Computers and Intractability: A Guide to the Theory of NP- Completeness

Improved Approximations of Independent Sets in Bounded-Degree Graphs
Efficient bounds for the stable set
On the Approximability of NP-complete Optimization Problems
On approximating the longest path in a graph.
On Syntactic versus Computational Views of Approx- imability
Approximation Properties of NP Minimization Classes.
On the hardness of approximating minimization problems.
Quantifiers and Approximation.

The traveling salesman problem with distances one and two.
The analysis of local search problems and their heuristics.
--TR

--CTR
Bruno Escoffier , Vangelis Th. Paschos, Completeness in approximation classes beyond APX, Theoretical Computer Science, v.359 n.1, p.369-377, 14 August 2006
Angel , Evripidis Bampis , Laurent Gourvs, Approximating the Pareto curve with local search for the bicriteria TSP(1,2) problem, Theoretical Computer Science, v.310 n.1-3, p.135-146, 01 January 2004
James B. Orlin , Abraham P. Punnen , Andreas S. Schulz, Approximate local search in combinatorial optimization, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
Jukka Suomela, Approximability of identifying codes and locating--dominating codes, Information Processing Letters, v.103 n.1, p.28-33, June, 2007
Cristina Bazgan , Bruno Escoffier , Vangelis Th. Paschos, Completeness in standard and differential approximation classes: poly-(D)APX- and (D)PTAS-completeness, Theoretical Computer Science, v.339 n.2, p.272-292, 12 June 2005
Friedrich Eisenbrand , Fabrizio Grandoni, On the complexity of fixed parameter clique and dominating set, Theoretical Computer Science, v.326 n.1-3, p.57-67, 20 October 2004
Alex characterization of NP with optimal amortized query complexity, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.191-199, May 21-23, 2000, Portland, Oregon, United States
Jianer Chen , Xiuzhen Huang , Iyad A. Kanj , Ge Xia, Polynomial time approximation schemes and parameterized complexity, Discrete Applied Mathematics, v.155 n.2, p.180-193, January, 2007
Moni Naor , Kobbi Nissim, Communication preserving protocols for secure function evaluation, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.590-599, July 2001, Hersonissos, Greece
Harry B. Hunt, III , Madhav V. Marathe , Venkatesh Radhakrishnan , S. S. Ravi , Daniel J. Rosenkrantz , Richard E. Stearns, Parallel approximation schemes for a class of planar and near planar combinatorial optimization problems, Information and Computation, v.173 n.1, p.40-63, February 25, 2002
approximation algorithms;computational classes;computational complexity;local search;complete problems;polynomial reductions