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

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

52 Chapter 3. Derandomization

In order to get an approximate solution we replace the constraints (3.9) by

x~ E [0, 1] and solve this linear relaxation of the 0-1-program. Linear programs

can be solved, e.g., by the simplex algorithm due to Dantzig [Dan63] or by

the ellipsoid algorithm due to Khachian [Kha79]. The latter algorithm has a

polynomial worst case run time. Both algorithms are also presented in [PS82].

Another method for solving linear programs with a polynomial worst-case run

time is the interior point method due to Karmarkar [Kar84].

Let/~k denote the solutions of the linear relaxation of the 0-1-program. Let W ~

be the value of the objective function for this solution. Now we apply randomized

rounding. In order to make sure that all constraints (3.10) are satisfied we per-

form the randomized rounding in such a way that from each set Aj exactly one

vector is chosen, where the vector V~ is chosen with probability 4" This is done

independently for all j. Let W E be the maximum of the left-hand sides of con-

straints (3.11) for the solution obtained by randomized rounding. For the value

W E of the objective function all constraints are satisfied. We see that for this

special 0-1-program randomized rounding always leads to solutions satisfying all

constraints. Of course, W E may be larger than W ~. A bound on W E in terms

of W ~ is given by the following theorem.

Theorem 3.8. There is a solution for the O-l-program where the value W E of

the objective function is bounded by W'. (1 + D(W', l/n)).

Proof. Let Zi be the random variable describing the i-th coordinate of ~j=l Vj"

Ek=l J J "

Then we have Zi ~-~'=1 ks = XkV ~ (z). Hence, Zi is the sum of those random

variables x~ for which Vg(i) = 1, i.e., a sum of Bernoulli trials. The mean of Zi

j=l

k=l

Since the /~k are a solution of the linear relaxation program, it follows from

constraints (3.11) that E[Zi] < W' for 1 ~< i < n. By definition of D(-, .) the

probability of Zi being larger than W'. (1 + D(W', l/n)) is less than 1/n. Since

there are n random variables Zi the probability that any Zi exceeds that bound

is less than 1. Hence, there is some solution for which all Zi do not exceed the

bound. 9

In order to derandomize the proof of Theorem 3.8 we need a slight generalization

of the results of the last subsection. The reason is that we have the choice

between k~ alternatives when performing randomized rounding, while the results

for

LATTICEAPPROXIMATION were derived for two alternatives. We omit this

straightforward generalization. The result is the following theorem.

Theorem 3.9. By the method of pessimistic estimators an integer solution for

which the value of the objective function is bounded by [W' 9 (1 + D*(W', l/n)) 1

can be obtained deterministically in polynomial time.

3.5. Reduction of the Size of the Probability Space 53

Since W ~ is an optimum solution for the linear relaxation, it is also a lower

bound on the optimum solution of the 0-1-program. The performance ratio of

the approximation can be estimated by applying formulae (3.4) and (3.5) to the

result of Theorem 3.9. It can be shown that the performance ratio is bounded

by some constant and that it converges to 1 as W ~ goes to infinity.

3.5 Reduction of the Size of the Probability

Space

Let A be some randomized polynomial time algorithm for some optimization

problem. If there is only a polynomial number of possible random choices for this

algorithm, then it is easy to obtain a deterministic polynomial time algorithm

from A. In polynomial time we can run A for all possible random choices and

select the best result. But in general the number of possible random choices is

not bounded by a polynomial. In this section we present a method that allows

to reduce the size of the sample space from which the random choices are done.

We start with an outline of the method. When analyzing some randomized algo-

rithm one usually assumes that the random choices are mutually independent.

The reason is that it is often much easier to handle independent random vari-

ables rather than dependent random variables. But sometimes it is possible to

analyze the randomized algorithm without the assumption of mutually indepen-

dent random choices. E.g., it may suffice for the analysis to assume pairwise or

d-wise independence. This weaker assumption on the independence may lead to

a weaker result on the expected performance ratio of the algorithm (cf. Exer-

cise 3.3).

We present a result which shows how to obtain a probability space (f~, P) and

d-wise independent random variables where the sample space f~ has only poly-

nomial size. But the distribution of these random variables is merely an ap-

proximation for the distribution of the random variables used in the analysis of

the randomized algorithm. Hence, one has to check whether the analysis is also

valid for these random variables with approximated distributions. Possibly the

analysis or even the algorithm has to be adapted. Finally, we can derandomize

the algorithm by trying all samples from the polynomial size sample space.

We apply this method to two examples. First we derandomize the randomized

algorithm for MAXE3SAT presented in Chapter 2. Then we show how to apply

this method to a parallel randomized algorithm for the problem of computing

maximal independent sets. In the derandomized version of this algorithm the

randomized algorithm is run for all samples of the polynomial size sample space

in parallel. This is possible by a polynomial number of processors.

54 Chapter 3. Derandomization

3.5.1 Construction of a Polynomial Size Sample Space and d-wise

Independent Random Variables

In this subsection we describe the method of Alon, Babai and Itai [ABI86] for the

construction of a polynomial size sample space and d-wise independent random

variables. First let us recall the definition of d-wise independence.

Definition 3.10.

The random variables

Xl,...

,Xn are called d-wise indepen-

dent if each subset consisting o/ d of these random variables is independent, i.e.,

if]or all 1 ~ il < ... < id ~ n and for all xl,... ,xd it holds that

Prob[Xh = x,,..., Xi~ =

Xd] =

Prob[Xi~ = xl]....- Prob[Xi~ =

Xd].

Alon, Babai and Itai [ABI86] consider the general case where the random vari-

ables may take an arbitrary finite number of values. For our purposes it suffices

to consider the special case where the random variables only take the two values

0 and 1. By the construction given in the proof of the following lemma, we obtain

a uniform probability space (f~, P), i.e., each elementary event in f~ has the same

probability 1/If~ I.

Lemma 3.11.

Let XI,...,Xn be random variables where each Xi only takes

the values 0 and 1. Let q be a prime power, q ) n and d >1 1. Then there

are a uniform probability space

(f~,

P), where If~l = qd, and d-wise independent

random variables X[,...,X~ over (f~, P) and it holds ]or each i e

{1,... ,n}

that

IProb[X~ = 1] - Prob[Xi -- 1]1 ~<

1/2q.

By the last condition we also have ] Prob[X~ = 0] - Prob[Xi = 0]1 ~<

1/2q.

Pro4 of Lemma 3.11.

Let Pi = Prob{Xi = 11 and let p~ =

rqp,

l1211q.

This means that we obtain p[ by rounding Pi to the nearest multiple of

1/q.

particular, we have IPi -P~I <~

1/2q.

Let Fq = {0,...,q- 1}, Ai,1 = {0,1...,qp~

1} and A~,0 =

{qp~,...,q-

1}.

Then

IAi,ll/IFq] = p~ and IAi,ol/IFql = 1-p~.

The sample space f~ consists of all

polynomials over Fq of degree at most d- 1.

The probability space is uniform, i.e., each polynomial is chosen with probability

1/q d.

The random variables X~ :f~ --+ ll~ are defined by X~(p) = 0 iff p(i) 9 Ai,o

and

X~(p)

= 1 if[

p(i) 9 A~,I.

Then Prob[X~ = 0] = 1 -p~ and Prob[X~ = 1] = p~. Hence, it holds that

IProb[X~ = 1]-

Prob[X~ = 111 <

1/2q.

In order to prove that the X~ are d-wise independent let 1 ~< il < ... <

id <. n.

For ~ 9 {1,..., d} let xe 9 {0, 1}. Then

3.6. Another Approximation Algorithm for MAxE3SAT 55

Prob[X~l = xl,..., X~ = xd] = Prob[p(il)

E Ah,~,... ,p(id) 9 Ai~,~].

There are IA~I,~I I'..." IAi~,~ I polynomials p fulfilling

p(Q) E AiI,~,... ,p(id) E

Ai~,x~, since p is a polynomial of degree at most d- 1 and, hence, it is uniquely

determined by fixing its value at d different places. Therefore,

Prob[p(Q)

E Ai~,x~,... ,p(id) e A~d,~]

- Prob[X~, = x~]..... Prob[X~ =

xd].

Hence, the X~ are d-wise independent.

We describe how to apply Lemma 3.11 for the derandomization of some ran-

domized algorithm. The random variables X1,..., Xn are the random variables

describing the random choices of the algorithm. We assume that the probabilities

for which X1,..., Xn take the values 0 and 1 are rational numbers. Hence, we

can compute the values p~. We replace

X1,..., Xn

by X~,..., X~n. Since Ill I is

bounded by some polynomial in n, we can consider all Ifll elementary events in

polynomial time or in parallel by a polynomial number of processors. For each

elementary event p we evaluate the random variables X~,..., X~, i.e., we com-

pute X~ (p),..., X~n (p) and run the given randomized algorithm for these values

of the random variables. From the [12] results a best one is selected.

The random variable

X~(p)

can be evaluated in constant time, if d is a constant.

We merely have to evaluate a polynomial of constant degree and to compare the

result with

qp~.

Hence, the evaluation of all X~(p) for all i E {1,... ,n} and all

p E fl is possible by an EREW PRAM with qd+l processors in constant time.

3.6 Another Approximation Algorithm for MAXE3SAT

In this section we show how Lemma 3.11 can be applied in order to derandomize

the algorithm RANDOM EkSAT ASSIGNMENT given in Chapter 2. The derandom-

ization only works for constant k and we only consider the case k = 3, i.e. the

algorithm for the problem MAXE3SAT. Recall that an instance of MAXE3SAT

consists of the set {xl,... ,xn} of variables and the set C = {C1,...

,Cm}

clauses. In the randomized algorithm each variable

xl,..., xn

is randomly and

independently chosen to be 0 and 1 with probability 1/2 each. Then the prob-

ability of a clause to be satisfied is 7/8 and the expected number of satisfied

clauses is 7/8. m.

It is easy to see that the same analysis works if xl,..., xn are chosen to be 0

and 1 with probability 1/2 each and if we only assume threewise independence

of Xl,..., xn. Hence, we may apply Lemma 3.11.

56 Chapter 3. Derandomization

We choose for q the smallest power of 2 such that q >/ n. Since the random

variables x~ take the values 0 and 1 with probability 1/2 each and since q is

even, we may apply Lemma 3.11 and replace x~ by X~ where Prob[xi = 1] =

Prob[X~ = 1]. In other words, the distribution of the random variables does not

change when applying Lemma 3.11.

The sample space fl consists of all polynomials p of degree 2 over Fq. Each such

polynomial can be represented by a triple

(r2,rl,ro) E ~qq

of its coefficients.

Hence, there are q3 such polynomials. By the proof of Lemma 3.11 we choose

X~(p) -- 0 iff p(i) E Ai,0 and X~(p) = 1 iffp(i) E A~,I. This can be done sequen-

tially in polynomial time for all polynomials of degree 2. Then the assignment

to the x~ satisfying the largest number of clauses is chosen. Hence, we obtain the

following algorithm.

DERANDOMIZED ALGORITHM FOR MAxE3SAT

Input: A set C = {C1,..., Cm} of clauses over the variables {xl,..., xn} where

each clause consists of exactly three literals.

let q be the smallest power of 2 such that q >/n

for all

(r2, rl,

r0) e ~q do

for i :-- 1,...,n do

(r2i 2

-~- rl~

"~- tO) mod q 9 (0,...,q/2

then

xi := 0

else

xi := 1

count the number of satisfied clauses

Output: An assignment to the x-variables maximizing the number of satisfied

clauses.

By the analysis given in Chapter 2 and by Lemma 3.11 the algorithm is an

approximation algorithm for MAXE3SAT with a performance ratio of at most

8/7. The algorithm runs in polynomial time, since q3 = O(n 3) iterations of the

for-all-loop are performed. For each iteration O(m + n) steps are sufficient. On

the other hand the derandomized algorithm described in Section 3.3 yields the

same performance ratio and is faster.

3.7 A PRAM Algorithm for MAXIMALINDEPENDENTSET

In this section we present a randomized parallel algorithm for MAXIMALINDE-

PENDENTSET due to Luby [Lub85, Lub86] and its analysis under the assumption

of mutually independent random variables. Then we show how to adapt the anal-

ysis and the algorithm for the case of pairwise independent random variables and

for the case that the distributions of the original random variables are merely

approximated. In this section we follow the presentations of Alon, Babai and

Itai [ABI86] and of Motwani and Raghavan [MR95b].

We do not discuss the implementation of the algorithm on an EREW PRAM.

For more details on EREW PRAMs see, e.g., [KR90].

3.7. A PRAM Algorithm for MAXIMALINDEPENDENTSET 57

3.7.1 A Randomized Algorithm for MAXIMALINDEPENDENTSET

We start with the definition of the problem.

MAXIMALINDEPENDENTSET

Instance: An undirected graph G = (V, E).

Problem: Compute a set I C_ V that is independent and maximal. Independent

means that there is no edge in E connecting nodes in I. Maximal

means that I is not a proper subset of some independent set.

Note that the problem is different from the AlP-complete problem of computing

an independent set of maximum size. The condition on a maximal independent

set is merely that we cannot obtain a larger independent set by adding nodes.

It is easy to compute a maximal independent set for a graph sequentially. Iter-

atively a node v is chosen and v and all neighbors of v are removed from the

graph. This is done until the graph is empty. Then the chosen nodes form a

maximal independent set.

By a similar idea we can obtain a fast parallel algorithm. Now we choose some

independent set S rather than a single node. Then all nodes in S and all neighbors

of nodes in S are removed from the graph. This procedure is iterated until the

graph is empty. Then the union of all chosen sets S is a maximal independent

set.

In order to make sure that this algorithm is fast it is essential that in each

iteration the number of removed nodes is large. In the following algorithm the

computation of S uses randomization. The algorithm is due to Luby [Lub85,

Lub86] and is also presented in [MR95b].

In the following the degree of some node v is denoted by

d(v).

For some node

set S let F(S) denote the set of all neighbors of S.

A RANDOMIZED PARALLEL ALGORITHM FOR MAXIMALINDEPENDENTSET

Input: A graph G -- (V, E).

I:=0

while V r 0

for

all v E V do in parallel

d(v) = 0

then I := I U {v}; delete v from G

else mark v with probability

1/(2d(v))

for all {u, v) e E do in parallel

if u and v are marked

then unmark the node with lower degree (if

d(u) = d(v),

then

unmark the node with the smaller number)

let S be the set of marked nodes

I := IUS

delete all nodes in S U F(S) from G

Output: The maximal independent set I.

58 Chapter 3. Derandomization

It is easy to check that at the end of each iteration of the while-loop the set S

is an independent set and that the algorithm eventually computes a maximal

independent set. By choosing

1/(2d(v)) as

probability for marking v, nodes with

smaller degree are marked with higher probability. This decreases the probability

of marking both endpoints of an edge. The analysis consists of the proof that the

expected number of edges deleted in some iteration (of the while-loop) is f~(IE* I)

where E* denotes the set of edges at the beginning of this iteration. Then the

expected number of iterations is O(log IEI) = O(log IVI). One may easily check

that each iteration can be performed by an EREW PRAM with

O(IV I +

IEI)

processors in time O(log IEI). Altogether, we shall obtain the following theorem.

Theorem

3.12.

A maximal independent set of a graph G = (V, E) can be com-

puted by a randomized algorithm on an EREW PRAM with O(IV I + IEI) pro-

cessors where the expected run time is

O(log 2 IVI).

For the analysis we assume that the random markings are mutually independent

for all nodes. In the following we consider only one iteration of the while-loop.

We call a node

v bad

if (at the beginning of the iteration) the degree of at least

2/3 of its neighbors is larger than the degree of v. Otherwise it is called

good.

An edge {u, v} is

bad

if u and v are bad. If at least one endpoint of an edge is

good, then the edge is called

good.

We show that the probability for each good

edge to be deleted in this iteration is at least some positive constant. Hence, the

expected number of good edges deleted in each iteration is at least a constant

fraction of the number of good edges at the beginning of the iteration. Together

with the fact that at least half of the edges of each graph are good it follows

that in each iteration f~(IE*l) edges are deleted.

Lemma

3.13.

Let v be a good node with a degree larger than O. Then during

an iteration with probability of at least 1 - e -1/6 some node w E

F(v)

is marked.

Proof.

There are at least

d(v)/3

neighbors of v with a degree at most

d(v)

since v is good. In order to estimate the probability that some neighbor of v is

marked, we consider only these nodes. Each node w among these neighbors of v

is marked with probability

1/(2d(w)) >1 1/(2d(v)).

Then the probability that at

least one of these nodes is marked is at least

1-(1 1 ~a(v)/3 e -1/6.

2d(v) ] i> 1 -

Lemma

3.14.

The probability that during an iteration some marked node w is

not unmarked is at least

1/2.

3.7. A PRAM Algorithm for MAXIMALINDEPENDENTSET 59

Proof.

A marked node w may get unmarked only if one of its neighbors with a

degree of at least

d(w)

is also a marked node. Let u be such a neighbor. Then u is

marked with probability

1/(2d(u)) <~ 1/(2d(w)).

The number of such neighbors

u is bounded by

d(w).

Then the probability of w not to become unmarked is at

least

1 1

1 - Prob[Bu 9 F(w): u is marked A

d(u) >/d(w)]

>t 1 -

d(w).

2d(w) = 2"

Since in each iteration exactly those nodes are deleted that are marked and not

unmarked, Lemma 3.13 and Lemma 3.14 imply the following lemma.

Lemma

3.15.

During an iteration the probability of a good node to become

deleted is at least

(1 - e-1/6)/2.

In order to complete the estimate of the expected number of iterations we apply

the following lemma. We omit the proof, which can be found in [ABI86] and in

[MR95b].

Lemma

3.16.

In each graph G = (V, E) the number of good edges is at least

IEJ/2.

By definition a good edge is incident to at least one good node. By Lemma 3.15

in each iteration each good node is deleted with probability at least (1-e-1/6)/2.

Hence, the same holds for each good edge. Since at least half of the edges are

good, the expected number of deleted edges is at least IE*I(1 - e-1/6)/4. This

completes the proof of Theorem 3.12.

3.7.2 Derandomization of the Randomized Algorithm for

MAXIMALINDEPENDENTSET

The derandomization of the algorithm of the last section is based on the obser-

vation that mutual independence of the random markings is not necessary for

the analysis of the algorithm. It suffices to assume pairwise independence. For

this case we obtain a slightly weaker version of Lemma 3.13. As in the analysis

of the randomized algorithm we consider only one iteration of the while-loop.

Let n be the number of nodes in the graph at the beginning of the iteration and

let E~ for i E (1,..., n} be the event that the i-th node is marked.

Lemma

3.17.

Assume that the events

El,...,

En are pairwise independent. Let

v be a good node with degree larger than O. Then during an iteration with prob-

ability of at least

1/12

some node w E

F(v)

is marked.

60 Chapter 3. Derandomization

Proof.

Let k be the number of neighbors of v with degree at most

d(v).

Since v

is good, we have

k >1 d(v)/3.

After renumbering the nodes we may assume that

the neighbors of v with degree at most

d(v) are

the first k nodes vl,..., vk. Then

El,..., Ek

denote the events that these nodes are marked. We have Prob[Ei] =

1/(2d(vi)) >>. 1/(2d(v)).

Define

sum

:= Ei=I

Prob[E~]. Then

sum >t k/(2d(v)) >1

1/6. The event that at least one node in F(v) is marked is [.Ji=l Ei. The claim

of the lemma follows directly from the following lemma due to Luby [Lub85]. 9

Lemma 3.18.

Let E1,...,Ek be pairwise independent events and let sum

~-~=1 Prob[Ei].

Then

Prob[l.J~=i

Ei]) min(sum,

1)/2.

A proof of this lemma can be found in [Lub85].

A careful inspection of the proof of Lemma 3.14 shows that this proof remains

valid even when replacing the mutually independent marking by pairwise inde-

pendent marking. Hence, the expected number of iterations of the algorithm is

also O(log IVI) when using pairwise independent marking. Let

be the random

variable describing the marking of the i-th node. We can apply Lemma 3.11 and

replace Xi by X~. For q we may choose the smallest prime larger than n. We ob-

tain a sample spa~e of size q2 __ O(IVI2). The iterations of the original algorithm

are derandomized separately. Each iteration is executed for all q2 polynomials in

f~ and the corresponding values of the X~ in parallel. A largest set S is selected

and all nodes from S t3 F(S) are removed from the graph.

The only problem is that the probability of marking a node was slightly changed

by applying Lemma 3.11. The probability of a node to become marked may

change by

1/2q.

Luby [Lub86] shows how to overcome this problem. Before

starting an iteration of the algorithm we search for a node v where

d(v) >/n/16.

If such a node v is found, v is included into I and v and all neighbors of v are

deleted. In this case at least 1/16 of the nodes of the graph are removed. This

implies that this situation may occur at most 16 times.

If no such node is found, for all nodes v we have

d(v) < n/16 <~ q/16

q /> 16d(v). Let v be the i-th node. Then IProb[Xi = 1]- Prob[X~ = 1]1 ~<

1/2q <<. 1/(32d(v)).

The probability that v is marked is at least 15/16-1/(2d(v))

and at most 17/16.1/(2d(v)). Now we have to check, whether the estimates in

Lemma 3.14 and Lemma 3.17 change.

In Lemma 3.14 the probability that some neighbor of u is marked is now bounded

by 17/16-

1/(2d(w)).

Hence, we obtain a slightly weaker version of this lemma.

Lemma 3.19.

If the events

El,...,

En are pairwise independent, the probability

that during an iteration some marked node w is not unmarked is at least

15/32.

In Lemma 3.17 the bound on the probability of

changes to 15/16-

1/(2d(w)).

Again we get a slightly weaker version.

3.7. A PRAM Algorithm for MAXIMALINDEPENDENTSET 61

Lemma 3.20.

Assume that the events

El,...,

En are pairwise independent. Let

v be a good node with degree larger than O. Then during an iteration with prob-

ability ol at least

5/64

some node w E

F(v)

is marked.

But the probability that a good node belongs to S t2 F(S) is still a positive

constant and, therefore, the number of iterations is O(log IVI). As described

above all polynomials in 12 can be tried in parallel. We have proved the following

theorem.

Theorem 3.21.

The problem ol computing a maximal independent set can be

solved by an EREW PRAM with

O(tVI 4)

processors in time

O(log 2

IVI). Hence,

MAXIMALINDEPENDENTSET E J~fC 2 9

Exercises

For the first two exercises we present a randomized algorithm for the problem

MAXCUT from [MR95b]. MAXCUT is considered in detail in Chapter 11. We

start with the definition of MAXCUT. An instance of MAXCUT is an undirected

graph G = (V, E). The task is to find a partition of the node set V into two sets

V1 and V~ so that the number of edges with one endpoint in V1 and the other

one in V2 is maximized.

A simple randomized approximation algorithm for MAXCUT works as follows.

Each node is put randomly and mutually independent in V1 or 112 with prob-

ability 1/2 each. For each edge the probability that one endpoint is in V1 and

the other one in V2 is 1/2. By linearity of the mean it follows that the expected

number of edges with endpoints in different sets is

IEI/2.

Since the size of a cut

cannot be larger than IEI, we obtain a randomized polynomial time approxima-

tion algorithm for MAXCUT with an expected performance ratio of at most 2.

Exercise

3.1. [MR95b] Derandomize this algorithm by the method of condi-

tional probabilities.

Exercise

3.2. Apply Lemma 3.11 for d : 2 in order to derandomize this algo-

rithm.

Exercise 3.3. We consider the algorithm RANDOM EkSAT ASSIGNMENT from

Chapter 2 for the case k = 3. Estimate the expected performance ratio of this

algorithm for MAxE3SAT for the case that the random choices are pairwise

independent rather than threewise or mutually independent. Derandomize the

algorithm by applying Lemma 3.11 for d = 2.