Wegener I. Complexity Theory. Exploring the Limits of Efficient Algorithms

Подождите немного. Документ загружается.

106 8 The Complexity of Approximation Problems – Classical Results

acceptable solutions, that is, the set of knapsack packings that do not violate

the weight limit. The idea is to decrease the utility values by replacing a

with



:= a

· 2

−t

 for some integer t>0. Figuratively speaking, we are striking

the last t positions in the binary representation of a

. If we choose t large

enough, then the utility values will be polynomially bounded. We solve the

instance x



with utility values a



.Thesolutions found in this way is optimal

for the instance x



with utility values a



:= a



· 2

as well. As solution s

∗

for

x we choose the better of solution s and the solution that simply chooses the

object with the largest utility a

max

. If we choose t too large, then x and x



are

too dissimilar and the solution s

∗

might not be good. If we choose t too small,

then the utility values are so large that the pseudo-polynomial-time algorithm

doesn’t run in polynomial time. But there is a suitable value for t so that the

approximation ratio is bounded by 1 + ε and the runtime by O(n

/ε). The

result is an FPTAS for

Max-Knapsack.

Here is a summary of the approximation ratios obtainable in polynomial

time:

• O(

log

)forMax-Clique,

• O(log n)for

Min-SetCover,

• 2for

Min-VertexCover,

• 8/7 for

Max-3-Sat,

• 3/2 for

Min-BinPacking,

• 3/2 for

Min-TSP



• PTAS for

Min-TSP

d-Euclid

• PTAS for

Min-VertexCover

planar

• PTAS for

Max-IndependentSet

planar

• FPTAS for scheduling on two processors,

• FPTAS for

Max-Knapsack,

• asymptotic FPTAS for

Min-BinPacking.

8.3 The Gap Technique

Now we investigate which approximation problems are diﬃcult. Since the

optimization problems we have considered are all

NP-easy, this is also true

for their respective approximation variants. If they are also

NP-hard, then

they are in fact

NP-equivalent. A central technique for this kind of result is

the so-called gap technique. The main principle of this technique is simple

to explain. If we have an optimization problem such that for every input x

and every solution s ∈ S(x)thevalueofs is not in the interval (a, b) (i.e.,

either v(x, s) ≤ a or v(x, s) ≥ b), and it is

NP-hard to determine which of

opt

(x) ≤ a and v

opt

(x) ≥ b holds, then it is NP-hard to obtain a worst-

case approximation ratio that is smaller than b/a. For an instance x of a

8.3 The Gap Technique 107

maximization problem with v

opt

(x) ≤ a, such an approximation algorithm

could output only solutions s with v(x, s) ≤ a. On the other hand, for an

instance x with v

opt

(x) ≥ b, the algorithm would need to provide a solution

with value v(x, s) such that

v(x, s) ≥ v

opt

(x) ·

>b·

= a.

But then the gap property implies that v(x, s) ≥ b.Thuswewouldbeableto

distinguish instances x with v

opt

(x) ≤ a from instances x with v

opt

(x) ≥ b.

The consideration of minimization problems proceeds analogously. We will

call problems of the type we have just described (a, b)-gap problems.

Remark 8.3.1. If an (a, b)-gap problem is

NP-hard, then it is NP-hard to obtain

a worst-case approximation ratio smaller than b/a for its optimization variant.

Buthowdoweget(a, b)-gap problems? Gap problems can arise from

polynomial reductions. If we reduce an

NP-hard problem to a decision problem

where we need to decide if an optimal solution to a maximization problem has

value at least b, and if the rejected inputs all have values at most a,thenwe

have an

NP-hard (a, b)-gap problem. It would be great if in Cook’s Theorem

the constructed instances of

Sat had a large gap, that is if either all the clauses

were satisﬁable or else at most some fraction α<1 of the clauses could be

satisﬁed. Unfortunately, the proof of Cook’s Theorem does not provide such a

result. We can always satisfy all the clauses except one by setting the variables

so that they simulate the computation of a Turing machine. Under such an

assignment, the only clause that might not be satisﬁed is the clause coding

that the ﬁnal state is an accepting state.

Nevertheless there are very simple applications of the gap technique. In the

polynomial reduction from

HC to TSP (Theorem 4.3.1), edges were replaced

with distances of 1, and missing edges were replaced by distances of 2. Round-

trip tours that come from a Hamiltonian circuit in the graph, have a cost of n.

Other tours have a cost of at least n + 1. This yields an

NP-hard (n, n + 1)-gap

problem. In this case, it is easy to increase the size of the gap by replacing the

distances of 2 with some polynomially long numbers, e.g., n2

.Thentours

that do not come from Hamiltonian circuits in the graph have cost at least

+ n − 1, so TSP is an NP-hard (n, n2

+ n − 1)-gap problem.

Theorem 8.3.2. If

NP = P, then there is no polynomial-time algorithm for

Min-TSP with a worst-case approximation ratio of 2

. 

So the traveling salesperson problem is in its general form hard even with

exponential approximation ratios, while the knapsack problem can be ap-

proximately solved with an FPTAS. This is an example of how analyzing

approximation variants provides a ﬁner complexity analysis than considering

only pure optimization variants. But it is seldom as easy as it is in the case

TSP to prove the diﬃculty of very large approximation ratios.

108 8 The Complexity of Approximation Problems – Classical Results

For most of the optimization problems we consider we obtain at least weak

inapproximability results. An optimization problem is called a problem with

small solution values if the values of all solutions are positive integers and

polynomially bounded in the length of the input. This is true of all scheduling

problems, covering problems, clique problems, team building problems, and

the optimization variants of veriﬁcation problems. It is also true for large

number problems like traveling salesperson problems, and knapsack problems,

if we restrict the numbers that occur in the input to have values bounded by

a polynomial in the length of the input. It is not immediately obvious how to

think up a problem that even when restricted to small numbers in the inputs

is not a problem with small solution values. Such a problem would arise, for

example, if we deﬁned the cost in a traveling salesperson problem to be the

product of the distance values.

Theorem 8.3.3. If

NP = P,thennoNP-hard problem with small solution

values has an FPTAS.

Proof. Let p(n) be a polynomial bound for the solution values. An FPTAS

for ε(n):=1/p(n) is a polynomial-time approximation algorithm since the

runtime is polynomially bounded in the length of the input n and 1/ε(n)=

p(n). Since we are assuming that

NP = P and that the problem is NP-hard,

this algorithm cannot compute an optimal solution for all inputs. Finally, the

solution values lie in {1,...,p(n)}, so every non-optimal solution shows that

the worst-case approximation ratio is at least

p(n)/(p(n) − 1) = 1 + 1/(p(n) − 1) > 1+ε(n) ,

which contradicts our assumption that there is an FPTAS. 

This result has consequences especially for optimization problems whose

decision variants are strongly

NP-complete. We will call these optimization

problems strongly

NP-hard. If the restriction to the NP-hard variant with

polynomial-size numbers is a problem with small solution values, then Theo-

rem 8.3.3 can be applied.

We get large gaps for optimization problems whose decision variants are

already

NP-complete for small numbers.

Theorem 8.3.4. If

NP = P and for some minimization problem with integer

solution values it is

NP-hard to decide whether v

opt

(x) ≤ k, then there is no

polynomial-time algorithm with a worst-case approximation ratio smaller than

1+1/k. The same is true for maximization problems and the decision whether

opt

(x) ≥ k +1.

Proof. We prove the contrapositive. We will use the polynomial algorithm A

with r

(n) < 1+1/k to solve the decision problem. An input x is accepted

if and only if A outputs a solution s with v(x, s) ≤ k. This decision is correct

because if there is a solution s



with v(x, s



) ≤ k but A outputs a solution

s with v(x, s) ≥ k + 1, then the worst-case approximation ratio is at least

(k +1)/k =1+1/k, a contradiction. 

8.4 Approximation-Preserving Reductions 109

Corollary 8.3.5. If NP = P, then Min-GC has no polynomial-time algorithm

with worst-case approximation ratio less than 4/3,and

Min-BinPacking has

no polynomial-time algorithm with worst-case approximation ratio less than

3/2.

Proof. For

GC the “≤ 3-variant” (Corollary 6.5.3) is NP-complete, and for

BinPacking the “≤ 2-variant” and even the special case of Partition are

NP-complete. 

Our results for

Min-BinPacking show that the notions “in polynomial time

achievable worst-case approximation ratio” and “in polynomial time achiev-

able asymptotic worst-case approximation ratio” are diﬀerent if

NP = P:The

ﬁrst parameter is 3/2 while the second is 1.

For

Min-GC there are much better results, but we want to use the classical

techniques we have already introduced to show that if

NP = P, then there is

no polynomial-time algorithm with asymptotic worst-case approximation ratio

less than 4/3. For this we consider a graph G =(V,E) with chromatic number

χ(G).

We will construct in polynomial time a graph G

=(V

)withχ(G

k · χ(G). The (3, 4)-gap will then become a (3k, 4k)-gap, i.e., a gap with

quotient 4/3 for arbitrarily large chromatic numbers. The construction ﬁrst

makes k disjoint copies of G and then adds an edge between two vertices if they

are in diﬀerent copies. In this way, each of the k copies must use a distinct

set of colors, and since each copy requires χ(G) colors, χ(G

) ≥ k · χ(G).

On the other hand, from an m-coloring of G we obtain a km-coloring of G

using k “shades” of each of the m colors. Each of the copies of G receives its

own “shade” but is otherwise colored according to the m-coloring of G. More

formally, if vertex v in G is colored with color c, then the corresponding vertex

in copy s of G in G

is colored with color (c, s). So χ(G

) ≤ k · χ(G).

In summary, we have used the results from Section 8.2 and the straight-

forward application of the gap technique under the assumption that

NP = P

to obtain the following results.

•

Max-Knapsack ∈ FPTAS − P,

•

Min-BinPacking ∈ APX − PTAS,

•

Min-GC /∈ PTAS,

•

Min-TSP /∈ APX.

The PCP Theorem, which will be presented in Chapter 12, provides a

method for applying the gap technique to many more problems.

8.4 Approximation-Preserving Reductions

Theorem 8.3.3 allows us to rule out the existence of an FPTAS for many prob-

lems under the assumption that

NP = P. Negative statements about contain-

ment in

PTAS and APX are rarer. For this reason we are interested in reduction

110 8 The Complexity of Approximation Problems – Classical Results

notions that would allow us carry over such conclusions from one problem to

another. What properties do we anticipate for the reduction notions “≤

PTAS

”

or “≤

APX

”? They should be reﬂexive and transitive, and A ≤

PTAS

B should

ensure that A ∈

PTAS if B ∈ PTAS. Of course, the analogous statements

should hold for ≤

APX

. As for polynomial reductions, the subprogram for B

will be called only once. Unlike for polynomial reductions, however, this call

cannot come at the very end. The result of a call to the subprogram is a solu-

tion for an instance of problem B, which typically cannot be directly used as

a solution for A. What we need is an eﬃcient transformation that turns good

approximation solutions for instances of problem B into “suﬃciently good”

approximation solutions for the given instance of problem A.

Deﬁnition 8.4.1. A PTAS reduction of an optimization problem A to an-

other optimization problem B (denoted A ≤

PTAS

B) consists of a triple

(f,g,α) of functions with the following properties:

• f maps instances x of problem A to instances f(x) of problem B and can

be computed in polynomial time;

• g maps triples (x, s, ε) where x is an instance of A, s ∈ S

(f(x)) is a so-

lution, and ε ∈ Q

, to solutions g(x, s, ε) ∈ S

(x),andg can be computed

in polynomial time;

• α : Q

→ Q

is a surjective polynomial-time computable function; and

• if r

(f(x),y) ≤ 1+α(ε), then r

(x, g(x, y, ε)) ≤ 1+ε.

We will see in our subsequent investigation that this deﬁnition satisﬁes

all our demands. Furthermore, these demands are “sparingly” met. So, for

example, g need only be deﬁned for instances of B that are produced by f

from instances of A.

Lemma 8.4.2. If A ≤

PTAS

B and B ∈ PTAS, then A ∈ PTAS.

Proof. The input for a PTAS for A consists of an instance x of A and an

ε ∈ Q

. In polynomial time we can compute f(x)andα(ε), apply the PTAS

for B on (f(x),α(ε)), and obtain an α(ε)-optimal solution y ∈ S

(f(x)).

Then we can compute in polynomial time g(x, y, ε) ∈ S

(x) and output the

result as a solution for x. The last property of PTAS reductions ensures that

g(x, y, ε)isε-optimal for x. 

Lemma 8.4.3. If A ≤

PTAS

B and B ∈ APX, then A ∈ APX.

Proof. Since B ∈

APX, there is a polynomial-time approximation algorithm

for B that computes δ-optimal solutions for some δ ∈ Q

. Since the function α

from the reduction A ≤

PTAS

B is surjective, there is an ε ∈ Q

with α(ε)=δ.

Now we can use the proof of Lemma 8.4.2 for this constant ε>0toobtain

a polynomial-time approximation algorithm for A that guarantees ε-optimal

solutions. 

8.4 Approximation-Preserving Reductions 111

This shows that we do not need a special reduction notion “≤

APX

”. For

the sake of completeness we mention that ≤

PTAS

is reﬂexive and transitive.

The statement A ≤

PTAS

A follows if we let f(x)=x, g(x, y, ε)=y,and

α(ε)=ε.If(f

,α

) is a PTAS reduction from A to B and (f

,α

)isa

PTAS reduction from B to C, then there is a PTAS reduction (f,g,α)from

A to C as illustrated in Figure 8.4.1, where f = f

◦ f

, α = α

◦ α

,and

g(x, y, ε)=g

(x, g

(x),y,α

(ε)),ε).

(x, ε)

y = g

(x, y

,ε)

ε-optimal for A

,α

(x),α

(ε))

= g

(x),y

,α

(ε))

(ε)-optimal for B

,α

◦ f

(x),α

◦ α

(ε))

PTAS

−−−−− →

for C

∈ S

◦ f

(x))

◦ α

(ε)-optimal for C

Fig. 8.4.1. The transitivity of PTAS reductions.

Some of the polynomial reductions that we have already designed turn out

to be PTAS reductions for the corresponding optimization problems with the

function g hidden in the proof of correctness.

Theorem 8.4.4.

Max-3-Sat ≤

PTAS

Max-Clique,and

Max-Clique ≡

PTAS

Max-IndependentSet.

Proof. For the ﬁrst statement we choose the transformation f from the proof

3-Sat ≤

Clique (Theorem 4.4.3). In the proof of correctness, we implicitly

showed how we can eﬃciently transform every clique of size k in problem f(x)

into a variable assignment of the original instance x that satisﬁes k clauses.

Weletthisvariableassignmentbeg(x, y, ε)andletα(ε)=ε.

The second statement follows analogously from the proof that

Clique ≡

IndependentSet (Theorem 4.3.4). In this case we can even set g(x, y, ε)=y

and α(ε)=ε, since a set of vertices that is a clique in G =(V, E)isan

anti-clique in

G =(V,E) and vice versa. 

Finally, the “inﬂation technique” described at the end of Section 8.3 for the

problem

Min-GC is an approximation-preserving reduction of that problem

to itself such that the transformation produces graphs with larger chromatic

112 8 The Complexity of Approximation Problems – Classical Results

numbers. But many of the polynomial reductions we have presented are not

approximation preserving. For example, if we consider the reduction showing

that

Sat ≤

3-Sat in the special case that the Sat-clauses each have length 4,

then m clauses for

Max -4- Sat become 2m clauses for Max -3- Sat,ofwhich

m clauses can be satisﬁed by giving all the new variables the value 1. So an

approximation ratio of 2 for Max -3- Sat has no direct consequences for the

given instance of

Max -4- Sat.

The proof of Theorem 8.4.4 shows that the problems

Max-Clique and

Max-IndependentSet have identical properties with respect to their approx-

imability. But Theorem 4.3.4 not only showed a close relationship between

Clique and IndependentSet, but also a close relationship between

IndependentSet and VertexCover.ForMin-VertexCover we know from

Section 8.2 a polynomial-time approximation algorithm with worst-case ap-

proximation ratio of 2. In the proof that

IndependentSet ≤

VertexCover,

the input graph was not changed, only the bound k was changed, namely to

n−k. From a vertex cover V



⊆ V we obtain the independent set V



= V −V



What does this mean for the approximability of

Max-IndependentSet? Noth-

ing, as the following example shows. Let the graph G =(V,E) consist of n/2

edges that have no vertices in common. The 2-approximation algorithm com-

putes the entire vertex set V



= V , which has an approximation ratio of 2.



is then the empty set, and is replaced with a better solution consisting

of a single vertex according to our comments in Section 8.1. The resulting

approximation ratio of n/2, however, is very bad. In fact, we will see in Chap-

ter 12 that

Max-Clique and Max-IndependentSet can only be very poorly

approximated.

8.5 Complete Approximation Problems

The success of the theory of NP-completeness leads to the question of whether

there is a class of optimization problems that can play the role of

NP,and

whether with respect to this class there is a class of ≤

PTAS

-complete problems.

The class

NP can be deﬁned as the class of problems for which given an in-

stance x and a polynomially long proof attempt y we can decide in polynomial

time whether y proves that x must be accepted by the given decision problem.

For optimization problems, the solutions play the role of these proofs.

Deﬁnition 8.5.1. An optimization problem A belongs to the complexity class

NPO (non-deterministic polynomial-time optimization problems) if for an in-

put (x, s) it is possible in polynomial time to check whether s is a solution

for x and, if so, to compute v(x, s). The class

NPO restricted to maximiza-

tion problems is denoted

Max-NPO, and restricted to minimization problems,

Min-NPO.

It is tempting to extend the containments between complexity classes for

approximation problems from Section 8.1 to

8.5 Complete Approximation Problems 113

⊆ FPTAS ⊆ PTAS ⊆ APX ⊆ NPO .

But by our current deﬁnitions it is not true that

APX ⊆ NPO. From every

decision problem, even non-computable problems, we obtain an

APX-problem

in the following way. For each instance x,letS(x)={0, 1} with 1 correspond-

ing to acceptance and 0 to rejection. Let the value of the correct decision be

2, and of the incorrect decision, 1. The corresponding maximization problem

belongs to

APX, since an output of 1 always has an approximation ratio of

at most 2. But if the decision problem is not computable, then the function

v(x, 1) is not computable either. Since

NPO contains all of the practically rel-

evant optimization problems, we will now restrict the classes

P, FPTAS, PTAS,

and

APX to problems in NPO, but continue to use the same notation. Once

we have restricted these classes in this manner, the containments listed above

are true.

Deﬁnition 8.5.2. An optimization problem A is

NPO-complete if it belongs

NPO and all problems from NPO can be ≤

PTAS

-reduced to A. APX-complete,

PTAS-complete, Max-NPO-complete and Min-NPO-complete are deﬁned analo-

gously.

We know from our study of

NP-completeness that the main problem will

be to ﬁnd the ﬁrst complete problem. After that, since the ≤

PTAS

-reductions

are transitive, it will suﬃce to reduce a known complete problem to another

problem from the class being considered. Not until Chapter 12 will we be able

to use the PCP Theorem to show that

Max-3-Sat is APX-complete. But there

is a problem that we can show is

NPO-complete using classical methods. As we

already know,

Sat-problems are good candidates for the “ﬁrst” complete prob-

lem. An instance of the maximum weight satisﬁability problem (

Max-W-Sat)

consists of clauses and non-negative integer weights for the variables that ap-

pear in them. The solution set consists of all variable assignments. The value

of a satisfying assignment is the maximum of 1 and the total weight of all the

variables that are assigned 1. The value of other variable assignments is 1.

Lemma 8.5.3.

Max-W-Sat is Max-NPO-complete.

Proof. Clearly

Max-W-Sat belongs to Max-NPO.NowletA ∈ Max-NPO.Our

task is to design a ≤

PTAS

-reduction of A to Max-W-Sat.ForA, we consider

the following nondeterministic Turing machine. For each instance x of A,the

machine nondeterministically generates a possible solution s. For this phase,

any sequence of symbols of length at most p(|x|) is allowed, where p(n)isa

polynomial bounding |s| for all s ∈ S(x)andallx with |x| = n.Nowwecheck

whether s ∈ S(x). If so, we compute v(x, s), write s and v(x, s)tothetape

and enter an accepting state. If not, we enter a rejecting state. The positions

where s and v(x, s) are written are the same for all inputs of the same length.

Now we apply the transformation from the proof of Cook’s Theorem to this

Turing machine. Finally, we give the weights of the variables. For each j,

114 8 The Complexity of Approximation Problems – Classical Results

the variable that codes whether the jth bit position of v(x, s)containsa1

receives the weight 2

. All other variables receive weight 0. This describes

the polynomial-time computable function f of the ≤

PTAS

-reduction we are

constructing.

Since for an instance x of A the solution set S(x) is not empty, there is

always at least one accepting computation, and therefore a satisfying assign-

ment for the instance of

Max-W-Sat. The reverse transformation g(x, y, ε)

computes the variables that describe the solution s in the output of the Tur-

ing machine from knowledge of x and the satisfying assignment y.Sowecan

compute s in polynomial time. Finally, we let α(ε)=ε.Ifthesolutiony for

the constructed instance of

Max-W-Sat codes the solution s ∈ S(x) for the

given instance x of A, then it also codes the value of v(s, x), and by the def-

inition of the variable weights, the weight of this assignment is v(x, s). So if

the solution for the

Max-W-Sat instance is ε-optimal, then the solution for

the instance x of A obtained with the help of g is also ε-optimal. 

Analogously we can deﬁne the problem

Min-W-Sat and show that it is

Min-NPO-complete. In fact, Max-W-Sat ≡

PTAS

Min-W-Sat. The proof is

conceptually simple, but some technical hurdles must be overcome. We will

not present this proof (see Ausiello, Crescenzi, Gambosi, Kann, Marchetti-

Spaccamela, and Protasi (1999)), but draw the following conclusion from

this result:

Theorem 8.5.4.

Max-W-Sat and Min-W-Sat are NPO-complete. 

The Complexity of Black Box Problems

9.1 Black Box Optimization

In practical applications randomized search heuristics such as randomized lo-

cal search, simulated annealing, tabu search, and evolutionary and genetic

algorithms have been used with great success. On the other hand, these al-

gorithms never appear in textbooks on eﬃcient algorithms as the best known

algorithms for any problems. This is also justiﬁed, since for a given problem,

a problem-speciﬁc algorithm will be better than general, randomized search

heuristics. The advantage of search heuristics is that they can be used for

many problems. Since they are not tailored to a particular problem, they ig-

nore much of the information that supports the design of eﬃcient algorithms.

This distinction between problem-speciﬁc algorithms and randomized search

heuristics is often unclear, since there are also hybrid variations, i.e., random-

ized search heuristics with problem-speciﬁc components. In that case, we are

dealing with problem-speciﬁc algorithms, i.e., with normal randomized algo-

rithms, which do not need any special treatment. Here we want to discuss

scenarios in which the use of problem-speciﬁc algorithms is not possible.

In real applications, algorithmic problems arise as subproblems in a larger

project. An algorithmic solution must be prepared in a short time, and experts

in the design of eﬃcient algorithms may not be available. In this situation “ro-

bust” algorithms, that is, algorithms that can be used to solve many problems,

oﬀer an alternative to craftfully designed, custom-ﬁt software.

It can even happen that the function to be optimized is not available in

closed form. When optimizing technical systems there are free parameters,

the setting of which inﬂuences the system. The search space or solution space

then consists of all allowed combinations of these parameters. Each setting of

the parameters inﬂuences the system and its ability to complete its assigned

task. So there is a function that assigns to each setting of the parameters

a value of the resulting system. But for complicated systems, this function

is not available in closed form; we can only derive these values by experi-

mentally testing the system with a particular setting of the parameters. In