Mayr E.W., Pr?mel H.J., Steger A. (eds.) Lectures on Proof Verification and Approximation Algorithms

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

1.4. Optimization and Approximation 21

(E(v(:~)) OPT(x) } r'

max OPT(x) ' E(v(~)) ~<

where

E(v(~))

denotes the expected value of ~.

1.4.2 Reduction concepts for optimization problems

In order to identify "hard problems" we define reduction concepts which allow

us to compare different optimization problems and to find complete problems.

The difficulty with reductions for optimization problems is that it is not enough

to map an instance for a problem to an instance for another problem. The ap-

proximability of the given instance and the instance it is mapped to have to be

related close enough to guarantee the desired ratio of approximation. Further-

more, the solutions for the second problem must admit the efficient construction

of a solution of similar ratio for the first problem.

It is quite obvious that two functions and not just one like for the polynomial

reductions (see Definition 1.6) are needed to construct a meaningful reduction for

approximation algorithms. But it is not at all obvious how the desired properties

concerning the approximation ratio can be guaranteed; so it is not too surprising

that different types of reductions for approximation were defined.

A reduction that reduces an optimization problem A to an optimization problem

B consists of three different parts, a function f that maps inputs x for A to inputs

y :--

f(x)

for B, a function g that maps solutions 9 for the input y for B to

solutions 5: :--

g(Y)

for A, and some conditions that guarantee some property

that is related with approximation. Given an approximation algorithm for B

one can construct an approximation algorithm for A in a systematic way. An

input for A is transformed into an input for B using f, then a solution for

.f(x)

is computed using the approximation algorithm for B, finally g is used

to transform this solution into a valid solution for x in the domain of A. This

interplay between f, g, and the approximation algorithm for B is sketched in

Figure 1.2.

The idea of approximation preserving reductions is not new and was already

stated in the early 80s by Paz and Moran [PM81]. The problem was that it

turned out to be very difficult to prove the completeness of an optimization

problem under the considered reduction type for a specific complexity class for

optimization problems, e.g. for

APX

and only very artificial problems could be

proven to be complete. A kind of shift happened at the beginning of the 90s

when Papadimitriou and Yannakakis [PY91] defined L-reductions. The defini-

tion of this new type of reduction they gave was tailored to fit together with a

new complexity class for optimization problem with a definition that does not

rely on the level of approximation the problems allow (what can be said to be

a computational point of view) but on a logical definition of AfT ~ due to Fagin

22 Chapter 1. Complexity and Approximation

problem A

inputs

problem B

inputs

approximation

solutions solutions

Fig. 1.2. Interplay of an (f, g)-reduction from A to B and an approximation

algorithm for B.

[Fag74]. The class is called MAX-SNP and is defined in two steps. Our descrip-

tion here relies on the book by Papadimitriou [Pap94]. In the original definition

by Papadimitriou and Yannakakis [PY91] MAX-SNP contained only maximiza-

tion problems though the authors mentioned that minimization problems can

be "placed" in MAX-SNP by reductions to maximization problems from MAX-

SNP. Here, we begin by defining the class MAX-SNP0 that can be described as

search for a structure S such that a maximal number of tuples

x = (Xl,..., Xk)

fulfill a term ~o(S, x) such that ~o is a quantifier-free term of first-order logic.

The class MAX-SNP itself consists of all problems from

AfPO

that can be L-

reduced to a problem in MAX-SNP0. Papadimitriou and Yannakakis proved

many natural problems to belong to the class MAX-SNP, so the definition of

this complexity class is not too restrictive. Using L-reductions they were able to

prove that MAX3SAT is complete for MAX-SNP. The relation between MAX-

SNP and computational based classes was not known for quite a time but it was

well known that if any MAX-SNP-complete problem has a polynomial approxi-

mation time scheme then all MAX-SNP-problems have. So, a problem could be

called hard to approximate if it was proven to be MAX-SNP-complete. In fact,

many problems were shown to be MAX-SNP-complete in the following years

and the notion of L-reduction became a widely accepted standard in the field.

However, the use of MAX-SNP instead of

APX

was caused by the difficulties

in proving natural problems to be A:PX-complete. Using another type of reduc-

tion, namely AP-reductions, allows to prove MAX3SAT to be

.4PX-complete,

so nowadays there is no need to formally define MAX-SNP and work with L-

1.4. Optimization and Approximation 23

reductions. As a consequence, we will continue by formally defining the so called

AP-reductions that were originally defined by Crescenzi, Kann, Silvestri, and

Trevisan [CKST95]. AP-reductions axe not the only alternative to L-reductions,

quite a lot of different reduction concepts were introduced that all have some fa-

vors and drawbacks. An overview and comparison of different reduction concepts

for optimization problems can be found in [CKST95]. However, AP-reductions

are approximation preserving and allow the identification of complete problems

for .APX, a fact that will be important in some of the following chapters.

Definition 1.32.

Let A

(IA, SA,

VA,

gOalA)

and B

(IB, SB, vB,

goalB)

be two optimization problems from AfT)O. We say that A is

AP-reducible

to B

~AP

B) if

there exist two functions f, g and a constant a > 0 such that the

following conditions hold:

1. Vx e I~, r > 1: I(x, r) e IB.

2. Vx 9 IA,r

> I : SA(X) # 0 ~ Sz(y(x,r)) # 0.

3. Vx 9 IA,r > 1,fJ 9 SB (f(x,r)) : g(x, ft, r) 9 SA(x).

4. The functions f and g can be computed in polynomial time for any fixed

r>l.

5. Vx 9 IA,r > 1,ft 9 Sz (f(x,r))

: max o,T(/(~,r)), ~,(~) 4 r

(max { .A(,(z,~,r))

oP,(z)

, } 1+ 1)).

The pair

(f,

g) is called an

AP-reduction.

If we specify a constant ~ we can call

the triple (f,g,a) an a-AP-reduction and write A <<.~,p B if A can be a-AP-

reduced to B.

The conditions 1-4 formalize our understanding of a reduction for optimization

problems; the interplay of the functions f and g is stated, the second condition

ensures that no "trivial reductions" are allowed. Without this condition it would

be possible to always map an input for A to an input without solution for B so

the third and fifth conditions come never into play making the reduction mean-

ingless. The fifth condition alone formalizes our understanding how a reduction

should connect the approximability of the two problems A and B. Refining Fig-

ure 1.2 for AP-reductions leads to a visualization as shown in Figure 1.3.

We will now follow Trevisan [Tre97] and show how AP-reductions can be used

to prove MAX3SAT to be complete for

APA'.

Theorem

1.33.

[Tre97]

MAX3SAT

is .AT~X-complete.

24 Chapter 1. Complexity and Approximation

problem A

inputs

problem B

inputs

f(~) =

approximation (/

with ratio 1 + a(r - 1) \

=a(~) --

solutions solutions

approximation

with ratio r

Fig. 1.3. Interplay of an a-AP-reduction from A to B and an r-approximation

algorithm for B.

Proof.

Khanna, Motwani, Sudan, and Vazirani [KMSV94] proved that for any

APX-minimization problem A there exists an APX-maximization problem B

such that A can be reduced to B by a reduction for optimization problems that

is called E-reduction. We adopt the method of this proof to show the same for

AP-reductions.

Let

A := (IA, SA, VA,

min) be a minimization problem from

A'PX.

Then there is

an approximation algorithm

for A that yields a solution ~ for an instance

x such that OPTA(~)~A(~) ~ C holds for some constant c and any input x. We define

B := (IA,SA,VB,max) as

follows. Let

x E IA

be an input for B, let ~ be the

solution that

yields for x and let ~ E

be any solution for x. Then we

define

VB(~) := max { [(c +

1)VA(X) -- CVA(y)], VA(:~)}. We claim that B belongs

APX.

To proof this we show that

is an approximation algorithm for B

with constant performance ratio. Obviously,

VB(bC) = VA(~)

holds so we have

OPTB(X ) ---- [(C-~-1)VA(:~)-

cOPTA(X)].

So, we can conclude for the perfor-

mance ratio of

MA as

approximation algorithm for B

:l.),,,,(i)- co,>, A(z)l

- ~< -- ~<c+l.

We claim that with f(x, r) := x and

g(x, ~), r) :=

VA(fl) < VA(bC)

VA(~) ~ VA(~)

1.4. Optimization and Approximation 25

we define an AP-reduction (], g) from A to B. Without loss of generality we

may assume that c is an integer. Assume

OPTB(X) ~

rVB(y)

holds. By the

considerations above we can deduce that (c +

1)VA(X) --cOPTA(X) ~

rVB(y)

holds. We distinguish two cases. First, assume that

vB(~9) = VA(~)

holds. We

then have (c+ 1-

r)vA(~C) <~ cOPTA(X),

vA( ) 1

OPTA (X) OPTA (X)

<~l+(r-1)c+l_ r

follows.

Now, assume that vs(~) = (c + 1)VA(~) -- CVA(~) holds. Then,

rcvA( ) cOeTA(z) + (r - 1)(c + 1)vA( )

follows and we have

vA( )

OPTA(X) ~ 1 + (r -- 1)(c + 1).

So, we indeed defined a (c + 1)-AP-reduction from A to B.

From the transitivity of AP-reductions if follows that it is sufficient to show that

any .47)X-maximization problem A can be AP-reduced to MAX3SAT.

Since A belongs to

.4PX

we may assume that

is an approximation algorithm

for A with performance ratio c.

To complete the proof we need two results as tools that will both be used but

not proven in this section. The first tool follows directly from Cook's theorem

[Coo71]. Given an AlP-problem H for any input w to H we can compute in

polynomial time an instance 9 for SAT such (~ is satisfiable if and only if w is

accepted by a Turing machine for II. As we discussed in Section 1.2 (page 10)

an Af:P-decision problem can be decided by a nondeterministic Turing machine

that guesses a proof for the membership of the input in the language and verifies

it. This "proof" can be viewed as a "solution" for the decision problem H; we

will clarify this statement when we make use of this tool.

The second tool relies on a statement that can be proven to be equivalent to the

PCP-Theorem (see Chapter 5). It uses a special version of SAT that is called

ROB3SAT and has the following properties. For some constant ~ > 0 either there

is an assignment that satisfies all m clauses of an instance or for all assignments

there are at least em clauses that are not satisfied. The statement we need here

is the following and is discussed in Chapter 4. There is a constant ~ > 0 such

that given an instance 9 for SAT it is possible to compute in polynomial time

an instance ~' for ~-ROB3SAT such that r can be satisfied if and only if 9 can.

F~rthermore, given an assignment that satisfies more than (1 -

clauses of

(h t we can compute in polynomial time an assignment that satisfies ~.

So, we now can assume that A --

(IA,SA,VA,max)

is an APX-maximization

problem,

is an approximation algorithm for A with performance ratio c,

26 Chapter 1. Complexity and Approximation

and v is the constant for ROB3SAT. We have to define f, g, and a so that

(f, g, a) is an AP-reduction from A to MAX3SAT; we write B for MAX3SAT in

the following. We have to show that OPTB (x) OPTa (x)

v~(~) ~< r implies -a(~) ~< l+c~(r--1) for

a constant a that we will specify later. We distinguish two cases. First, assume

that 1 + c~(r - 1) /> c holds; in this case the approximation given by

already good enough. So, we see it is sufficient to use the solution ~ that

yields for the input x to fulfill the property of an AP-reduction and we define

g(x, ~1, r)

:= ~ in this case.

Let now d := 1 + a(r - 1) < c hold. Since we have the approximation algorithm

with performance ratio c that yields a solution & for an input x we know that

the value of an optimal solution

OPTA(X)

is in the interval [VA(~), CVA(~)]. We

divide this interval in k := [log d c] subintervals with lower bounds

divA(~) and

upper bounds

di+lvA(5C)

for 0 x< i < k. Since

A E APX C_ AfPO

the problem

of deciding whether the value of an optimal solution is at least q belongs to

AlP for all constants q. We now have k AlP-decision problems such that the

"membership proof" we mentioned in the discussion of Cook's theorem is a

solution for our optimization problem A with value at least

divA(~).

Using the

second tool mentioned above we can compute in polynomial time an instance

for c-ROB3SAT qo with m clauses that is equivalent to the i-th A/'T'-decision

problem for all 0 ~< i < k. Given an assignment Ti that satisfies more than

(1 - e)m clauses we can compute in polynomial time a satisfying assignment

for qoi and use this to compute a solution

s E SA(X)

to the i-th AlP-decision

problem with

VA(S) >1 divA(SC).

We assume without loss of generality that each instance qoi has the same number

m of clauses; using an appropriate number of copies of ~i suffices to achieve

this. With io we denote the maximum index i such that qoi is satisfiable; we

k--1

have

diOvA(~) <<,

OPTA(X) •

d/~ then. We define 9 := Ai=0 ~i as

the instance for MAX3SAT. Assume that T is an assignment for 9 such that

OPTB(~IJ ) ~ rVB(T )

holds. We can use T as an assignment of qoi for all i by

ignoring all assignments for variables that do not occur in ~i. If T satisfies more

than (1 - e)m clauses in qoi for some i then qo, is satisfiable. We know that we

can compute in polynomial time a satisfying assignment for qoi; from Cook's

theorem we know that this assignment can be used to compute deterministically

in polynomial time a membership proof for the input to II, in this case this proof

is a solution for the problem of finding a solution to our optimization problem A

with value at least

divA

(~). Given the assignment T we are able to compute such

a solution deterministically in polynomial time. It follows, that if we can show

that T satisfies at least (1--e)m clauses in ~i0 we can compute in polynomial time

a solution with value at least

di~

that has ratio at most d = 1 + a(r - 1).

So, the defined reduction would indeed be an AP-reduction and the proof would

be complete.

We are still free to define the constant a and will use this freedom to show that

~- satisfies more than (1 -e)m clauses in qo~ o. We know that

OPTB(~I ~) ~ rUB(T)

holds

so OPTB(~I t) --VB(7")

<~ ~

OPTB(~I t)

r~rlkm

follows. We call the

1.4. Optimization and Approximation 27

number of clauses in ~o~ that ~- satisfies (1 - r and get

OPTB(IIJ ) --

VB(T)

m -- (1 -- e0)m = ~0m. Combining the two inequalities we can conclude that

Eo ~< ~ k holds. Obviously, it is sufficient to prove that ~ > k r_~ holds for any

r > 1. Recall that we defined k as [log d c] with d = 1 + a(r - 1). So we want to

prove

[ lnc ] r-1

r ln(l+a(r-1)) " r '

so it is sufficient to have

c (2r-2)/(6r) - 1

r-1

which is possible for a constant a since the right hand side of the inequality is

monotone decreasing for all sufficiently large r and converges to a constant for

r --+ 1. 9

As mentioned above, the class MAX-SNP and along with it L-reductions were

the standard topics in the area of approximation. This implies that it is desirable

to show the relations between the "syntactical class" MAX-SNP and the "com-

putational class" .AT~X. But from the definition of L-reductions it took several

years before the relationship between MAX-SNP and ,4PX was discovered. The

key idea is to find a way that allows the class MAX-SNP to be brought together

with the reduction concepts defined along with .APX. This can be done by con-

sidering the closure of MAX-SNP. The closure of a class g under a certain type

of reduction is the set of all problems L E AlP(P such that L can be reduced to

some problem in C. By Khanna, Motwani, Sudan, and Vazirani [KMSV94] it was

shown that using E-reductions the closure of MAX-SNP equals the subclass of

.APX which contains all problems from .APX that have only solutions with values

that are polynomially bounded in the length of the input. Using AP-reductions

it is possible to show that the closure of MAX-SNP equals ,4PX' so finally the

more artificial class MAX-SNP and the more natural class ,4PX' were unified.

Exercises

Exercise 1.1. Proof that AlP C_ BPP implies that AlP equals T~P.

Exercise 1.2. Place BPP in the polynomial hierarchy PT/, i.e. try to find the

smallest i such that BPP can be proven to belong to the i-th level of PT/.

Exercise 1.3. Assume that L is an AlPO-optimization problem with the fol-

lowing properties. For any input x the values of all solutions from S(x) are

positive integers, the optimal value

OPT(X)

is bounded above by a polynomial

in both the length of x and the maximal number appearing in x, and the under-

lying language of L is A/P-hard in the strong sense: it remains AlP-hard even

28 Chapter 1. Complexity and Approximation

if all numbers in the input are bounded above by a polynomial p in the length

of the input. Show that under the assumption P ~ AlP the problem L can not

belong to ,T'PTAS.

2. Introduction to Randomized Algorithms

Artur Andrzejak

2.1

Introduction

A randomized algorithm is a randomized Turing machine (see Definition 1.10).

For our purposes we can consider such an algorithm as a "black box" which re-

ceives input data and a stream of random bits for the purpose of making random

choices. It performs some computations depending on the input and the random

bits and stops. Even for a fixed input, different runs of a randomized algorithm

may give different results. For this reason, a description of the properties of

a randomized algorithm will involve probabilistic statements. For example, its

running time is a random variable.

Randomized algorithms may be faster, more space-efficient and/or simpler than

their deterministic counterparts. But, "in almost all cases it is not at all clear

whether randomization is really necessary. As far as we know, it may be possible

to convert any randomized algorithm to a deterministic one without paying any

penalty in time, space, or other resources" [Nis96].

So why does randomization make algorithms in many cases simpler and faster?

A partial answer to this question gives us the following list of some paradigms

for randomized algorithms, taken from [Kar91, MR95b].

Foiling the adversary. In a game theoretic view, the computational complexity

of a problem is the value of the following two-person game. The first player

chooses the algorithm and as answer the second player, called the adversary,

chooses the input data to foil this particular algorithm. A randomized algorithm

can be viewed as a probability distribution on a set of deterministic algorithms.

While the adversary may be able to construct an input that foils one (or a small

fraction) of the deterministic algorithms in the set, it is difficult to devise a single

input that would foil a randomly chosen algorithm.

Abundance of witnesses. A randomized algorithm may be required to decide

whether the input data has a certain property; for example, 'is a boolean formula

satisfiable?'. Often, it does so by finding an object with the desired property. Such

an object is called a witness. It may be hard to find a witness deterministically

if it lies in a search space too large to be searched exhaustively. But if it can be

shown that the search space contains a large number of witnesses, then it often

30 Chapter 2. Randomized Algorithms

suffices to choose an element at random from the space. If the input possesses

the required property, then a witness is likely to be found within a few trials.

On the other hand, the failure to find a witness in a large number of trials

gives strong evidence (but not absolute proof) that the input does not have the

required property.

Random sampling. Here the idea is used that a random sample from a pop-

ulation is often representative for the whole population. This paradigm is fre-

quently used in selection algorithms, geometric algorithms, graph algorithms and

approximate counting.

2.2 Las Vegas and Monte Carlo Algorithms

The popular (but imprecise) understanding of Las Vegas and Monte Carlo algo-

rithms is the following one. ALas Vegas algorithm is a randomized algorithm

which always gives a correct solution but does not always run fast. A Monte

Carlo algorithm is a randomized algorithm which runs fast but sometimes gives

a wrong solution. Depending on the source, the definitions vary. We allow here

that an algorithm stops without giving an answer at all, as defined in [Weg93].

Below we state the exact definitions.

ALas Vegas algorithm is an algorithm which either stops and gives a correct

solution or stops and does not answer. For each run the running time may

be different, even on the same input. The question of interest is the probability

distribution of the running time. We say that a Las Vegas algorithm is an el~icient

Las Vegas algorithm if on every input its worst-case running time is bounded by

a polynomial function of the input size.

A Monte Carlo algorithm is an algorithm that either stops and does not answer

or stops and gives a solution which is possibly not correct. We require that

it is possible to bound the probability of the event that the algorithm errs. For

decision problems there are two kinds of Monte Carlo algorithms. A Monte Carlo

algorithm has two-sided error if it may err when it outputs either

YES or NO.

It has a one-sided error if it never errs when it outputs NO or if it never errs

when it outputs

YES.

Note that a Monte Carlo algorithm with one-sided error is

a special case of a Monte Carlo algorithm with two-sided error.

The running time of a Monte Carlo algorithm is usually deterministic (but some-

times also algorithms in which both the running time and the correctness of the

output are random variables are called Monte Carlo algorithms). We say that a

Monte Carlo algorithm is an el~icient Monte Carlo algorithm if on every input

its worst-case running time is bounded by a polynomial function of the input

size. The nice property of a Monte Carlo algorithm is that running it repeatedly

makes the failure probability arbitrarily low (at the expense of running time),

see Exercises 2.1 and 2.2.