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

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

296 Chapter 11. Semidefinite Programming

Sketch of Proof. By numerical computation, analyze the approximation ratio

of the following modification of the algorithm described in Section 11.6.2:

9 Add the constraints listed in Section 11.8.1.

9 Use function (11.15) for nonuniform rounding.

In the analysis, first discretize the space of all vectors vo, vi, vj that satisfy the

additional constraints. In fact, it is sufficient to discretize the space of all possible

angles between vo, vi and vj. Then, numerically compute the ratio between the

probability that a clause is satisfied and the contribution of that clause to the

objective function. Check that this ratio is at least 0.931 for all these vectors. 9

The importance of the additional constraints is stressed by the fact that, for

nonuniform rounding using this function f, the worst case of the performance

ratio is attained for a triple of vectors where vi 9 vo + vj 9 vo + vi 9 vj = -1.

Using the same method with a different function f, Feige and Goemans obtain

Theorem 11.18 ([FG95]). MAXDICUT can be approximated by a randomized

polynomial-time algorithm with approximation ratio 0.859.

11.9 Modeling Maximum Independent Set as a

Semidefinite Program?

Just for didactical purposes, we consider how one might turn MAXIMUMINDE-

PENDENTSET into a semidefinite program. We leave to the interested reader the

investigation whether this can be used to obtain better approximation algorithms

for MAXIMUMINDEPENDENTSET than are currently known.

MAXIMUMINDEPENDENTSET

Instance:

Given an undirected graph G = (V, E).

Problem: Find a subset VI C V such that V1 does not contain any edge and

I Vll is maximized.

We first claim that the size of a maximum independent set in a graph (and

the corresponding independent set) can be obtained by finding a solution to the

following mathematical program:

max xl + .. . + xn - Z xixj

such thatVi:

0<~xi~l (11.16)

Then, the following mathematical program also yields the optimum:

11.9. Modeling Maximum Independent Set as a Semidefinite Program? 297

max x 2+...+x n- Z xixj

such that

Vi: 0~xi~l (11.17)

{i,j}eE

This follows from the observation that the objective function considered in one

variable only (others fixed) is a parabola which is open into the positive y-

direction. Hence, we have a guarantee that for either

xi = 0

or xi = 1, the

optimum is obtained.

Now, let us show that (11.16) represents MAXIMUMINDEPENDENTSET. Given an

independent set I and setting xi = i for i E I (and

xi = 0

otherwise), we see that

the optimal solution of (11.16) is at least the size of a maximum independent

set.

Assume that we are given a solution of (11.16). Since the objective function is

linear in every variable, we can assume that all xi are either 0 or 1. We construct

an independent set I with the same value as the objective function as follows:

If the set I := (i I xi = 1} is not an independent set, we proceed as follows: If

xi = xj = 1 and {i,j}

is an edge in the graph, then we set xi = 0 which means

that we have not decreased the objective function. (One vertex was eliminated,

but at least one edge was also removed.)

Hence, the optimal solution of (11.16) or (11.17) yields the optimum cardinality

of an independent set. Since by Theorem 4.13

MAXIMUMINDEPENDENTSET can-

not be approximated within a factor n e (unless P = ALP), it is unlikely that we

can solve this mathematical program with the help of semidefinite programming,

although it looks very much like the problem formulation for MAXCUT.

Consider for example the following semidefinite program P:

maximize

Yl,1 -{- "'" -{-

Yn,n - ~ Yl,j

such that

Y is PSD

{i,j)eE

We may also add the linear inequalities 0 ~< Yi.j ~< 1 to P. Since this semidefi-

nite program is a relaxation of (11.17), we have obtained a method to compute

an upper bound, unfortunately, this upper bound is useless, as the value of

the semidefinite program always is n, since one can choose Y to be the iden-

tity matrix. The question remains whether there are more suitable relaxation

approaches for

MAXIMUMINDEPENDENTSET.

Exercises

Exercise II.I. Given the following sets Mi,

- M1 = {(xl, x2) :

~1 ~ 3~2, Xl

~ 1},

- M2 = {(=1,x2) : xlx2 >/1,~1 >/0,x~ >/0},

298 Chapter 11. Semidefinite Programming

- M3 = {(xl,x2): x~ + x~ ~ 1}

- M4 = {(xl, x2): ~ + ~ <~ 1}

construct matrices F ~ F~ and F 2 such that

M/= {(xl,x2) : The matrix

Fi(Xl,X2) := F ~ + xl . F~ + x2 . F 2

is PSD}.

Exercise 11.2. Find an optimal solution to the semidefinite program (11.1)

(parabola and line).

Exercise 11.3. Derandomize the approximation algorithm for MAxCUT which

is described in Section 11.5.1.

Exercise 11.4. Let -1 ~< yi ~ 1,i = 1,...,T and let Ys~rn :=

~T=lY~ <~ O.

Prove the following: If Ys,m is fixed, then the Yi for which ~i arccos(yi) attains

a minimum, fulfill the following property:

There is a value Y ~< 0 and an r with

T/2 <~ r <~ T

such that r of the Yi are

equal to Y and T - r of the yi are equal to one.

12. Dense Instances of Hard

Problems

Katja Wolf

Optimization

12.1 Introduction

Some years ago only very few optimization problems like

KNAPSACK were

known

to have polynomial time approximation schemes. Since the PCP-Theorem im-

plies that all APX-hard problems are unlikely to permit a PTAS, a consequent

approach is to look for those subclasses which are easier to handle with respect to

approximation. Baker [Bak94] shows that several A/P-hard graph problems have

a PTAS on planar graphs. Chapter 13 is devoted to the construction of PTASs

for the TRAVELING

SALESMAN

problem and the k-MsT problem in Euclidean

metric spaces. Recently, research has been extended to the approximability of a

large class of problems, including MAXCUT and MAxEkSAT, on dense instances.

The topic of this chapter is to survey the approximation results that have been

achieved in this area.

We give a definition of density which depends on the type of the problem we

consider.

Definition

12.1.

A graph with n vertices is

dense

if it has

~(n 2)

edges. It is

everywhere dense

if the minimum degree of the graph is f~(n). A

kSAT

formula

in n Boolean variables is

dense

if it consists of f~(n k) clauses.

We shall follow the work of Arora, Karger and Karpinski [AKK95a], who com-

bine randomized sampling and rounding techniques with linear programming

to design a scheme with additive approximation guarantee for smooth integer

programs.

Definition

12.2.

Let p E

Z[xl,...,xn]

be a degree d polynomial with integer

coel~icients, p is called

smooth,

if the coej~icients preceding each term of degree

i are bounded by a constant factor times n d-i.

A smooth degree d integer program

has the objective

maximize

(minimize) p(xl,...,Xn)

subject to x~E {0,1} for l~<i~n.

The central result is the following theorem.

300 Chapter 12. Dense Instances of Hard Optimization Problems

Theorem 12.3. Let Opt denote the optimal value of the objective function of

a smooth degree d integer program. For each ~ > 0 there is an n O(1/e2) time

algorithm computing a 0-1 assignment to the variables which satisfies

p(xl,...,Xn) >1 Opt - end for a maximization problem, and

p(xl,...,Xn) <~ Opt + end for a minimization problem.

As we will see, the approximation scheme with additive performance guarantee

yields a (multiplicative) PTAS when applied to dense instances of the optimiza-

tion problems we are concerned with. But first, let us describe the underlying

ideas, treating MAXCUT as an example. We defer the proof of the theorem until

Section 12.3.

12.2 Motivation and Preliminaries

Let G = (V,E) be an undirected graph with vertex set V, (IV[ = n), and edge

set E. F(v) := {u 9 V [ (u, v) 9 E} denotes the set of vertices adjacent to vertex

v. The MAXCUT problem is to determine a set W C V such that the number of

edges having one endpoint in W and the other endpoint in V - W is maximized.

We can easily formulate MAXCUT as a smooth quadratic integer program if we

introduce a variable Xv for each vertex v 9 V:

maximize ~ ((1-x~)- ~ x~)

vEV uEr(v)

subject to xve{0,1}, v9

Let us interpret Xv = 0 as "v is on the left-hand side W" and xv -- 1 as "v is on

the right-hand side V - W" of the cut. In the above sum we count for each left

vertex the number of its neighbors on the right.

In a maximum cut each vertex must be situated opposite to the majority of its

neighbors, because otherwise one could move a vertex and increase the number

of edges crossing the cut. So, we could determine the position of a vertex, if we

knew to which side most of its neighbors belong. It seems as if nothing is won,

since we do not know the neighbors' positions either.

A useful trick in order to cope with this circularity is taking a sample and fixing

the positions of the sampled vertices arbitrarily. For the size of the sample we

choose k = O(log n).

Once we have arranged the sampled vertices, we could place each unsampled

vertex opposite the majority of its sampled neighbors. This will not be successful,

unless the numbers of right and left sampled neighbors differ a great deal. But

a different approach is more promising: By inspecting the sample, we can for

12.2. Motivation and Preliminaries 301

each vertex estimate the

]raction

of its neighbors that should be part of the

right-hand side.

In order to explain the progress we have made, we need some notations.

r v :~

8 v :

u 9 r(v)

rv is the number of v's neighbors

on the right-hand side of the cut.

an estimate for rv. Count v's right-hand side neighbors

in the sample and multiply the result by

n/k.

The Sampling Lemma (which we will prove in Section 12.2.3) guarantees that, if

we choose a sample of size k = O(logn/r with high probability sv and rv will

differ by an additive error of at most ~ n. We can restate the objective function

maximize Z (1 - xv). r~

vEV

and search for a solution to the following approximate system with 2n linear

inequalities:

maximize

Z (1-

xv) .sv

vEV

e r(~)

Z xu >I sv

u e r(v)

x~ E {0,1},

veV.

Note that we now have converted the original quadratic MAXCUT program into

a linear program. The reduction of the degree is a benefit of the sampling.

We obtain a fractional solution 0 ~<

Xv <~ 1 (v E V)

by linear programming

and afterwards apply Raghavan and Thompson's randomized rounding method

[RT87] to produce a 0-1 assignment.

Thus far, we have described a single run for an arbitrary allocation of the sample.

We repeat the same procedure for each of the 2 k = poly(n) possible arrange-

ments of the vertices in the sample. Of course, we implicitly consider the optimal

constellation of the sampled vertices among our trials. This technique is often

called

exhaustive sampling.

In the end, we take the assignment that yields the

largest cutsize.

It remains to be shown that the resulting approximation is within an additive

error of ~ n 2 of the optimum. The proof is given in Section 12.3.

Z xu ~< sv § ~n

302 Chapter 12. Dense Instances of Hard Optimization Problems

12.2.1 Chernoff Bounds

Before we go into the details of randomized rounding and random sampling, let

us briefly review Chernoff bounds to gain insight into the technical background of

the method. The analysis of the rounding procedure is quite intricate, because we

allow negative coefficients and must derive suitable tail bounds for the deviation

of a random variable from its mean.

Lemma

12.4. Let X1, . . . , Xn be independent Bernoulli random variables,

Prob[X~ = 1] = Pi = 1 - Prob[Xi = 0].

and let Wl,..., wn e [0, 1]. X denotes the weighted sum of the Bernoulli trials,

X = ~-~inl w~X~, and # = E[X]. Then the following inequality holds

Prob [IX-~l >t] ~< 2e -2.~/" for t > O.

For a proof of the lemma we direct the reader to [Hoe63] or to [MR95b]. It is

conducted in a similar way as the proof of Theorem 3.5.

Corollary 12.5. For each f > 0 there is a constant c > 0 such that under the

assumptions of Lemma 12.4

Prob [I x-#l>c~] ~< 2n -s.

Pro@ We apply Lemma 12.4 with t := e ~]r~-n and e = ~ and obtain

Prob[IX-#l>c nlx/-n-i~] ~< 2e-2C~log n ~< 2n -2c2 ~<2n-I.

Lemma 12.6 (Positive and Negative Variables).

Let X1,..., Xn be independent Bernoulli random variables such that {1,... ,n}

is the disjoint union of two sets I and J, and 0 <<. wi <~ 1 for i E I, and

-1 <~ wj ~ O forj E J.

Then for each f > 0 there are constants Cl > 0 and c2 > 0 such that

Prob fIX - > cl ] .< c2n-s

Sketch of Proof. We define

X(1) = ZwiXi' #(1) = E[X(1)], X(2) = ~

wjXj,

~(2) = E[X(2)].

zEI jEJ

Note that IX -/x I ~< IX 0) - #(1)[ + I - X(2) - (-#(2))1, so we can apply Corollary

12.5 to X (1) and to -X (2) and combine the resulting inequalities appropriately. 9

Remark 12.7. As common in the literature, we use the term with high proba-

bility to express that the probability is 1 - n -n0) when n tends to infinity.

12.2. Motivation and Preliminaries 303

12.2.2 Randomized Rounding

After this technical intermezzo, we are now well-prepared for the rounding pro-

cedure.

Lemma 12.8 (Randomized Rounding).

Assume that x = (xl,..., Xn) T is a fractional solution to the linear program

Ax=b

O~xi~l (i = 1,...,n),

where the coefficients of the matrix A are O(1).

Randomly construct a 0-1 vector y = (Yl,.--,Yn) T by setting yi = 1 or yi = 0

for all i 9 {1,... , n} independently according to

Prob[yi=l] = xi = 1-Prob[yi=0].

Then, with high probability, y satisfies

A y :

(b 1 -~-O(~nlogn),...,b n

-~- O( nvf~-~ )) T

Proof. We have imposed that the coefficients of A are bounded, say a 0 9 [-c, c ]

for 1 <~ i,j <. n. If we define &q := ao/c , bi := bile and notice that

j=l j=l j=l

we can apply Lemma 12.6 to each row i of the system. So we have

"lZhijyj-bil<. cl v/-n log n

j=l

with probability at least 1 - c2n -I, respectively

[ ~aoy j -bi I <~ cc, v/'nlogn = O(v~logn)

j=l

with probability at least 1 - c2n -I. Now choose f >/ 2 and enforce that the

assertion holds for the whole system with probability 1 - c2n -I+1. 9

12.2.3 Random Sampling

Lemma 12.9 (Random Sampling with Replacement).

Let r be the sum of n numbers al,..., an E [-c, c]. By sampling with replacement

we choose k = O(logn/c 2) (not necessarily distinct) elements and compute their

sum s. Then, with high probability, we have

k E -en, r+en .

304 Chapter 12. Dense Instances of Hard Optimization Problems

Thus, we can take sn/k as an estimate for r, but we have to tolerate a linear

error term.

For convenience, we cite an inequality for continuous random variables due to

Hoeffding ([Hoe63], Theorem 2):

If Y1,... ,Yk are independent random variables and a ~< Y/~ b for i = 1,... ,k,

let Y 1/k k = E[Y], then

= Ei=I

Yi and p

Prob[lY-/~l~> t]<~

e -2kt2/(b-a)2

for t>0.

Proof of Lemma 12.9. Introduce a random variable Xi for the element drawn in

the i-th turn, and let X 1/k k X n

: ~i=1 ~. We have E[Xi] = 1In ~j=l aj for each

i, and since we draw with replacement, the Xi are independent and identically

distributed.

-- n

Observing E[X] = 1/n ~j=t a3, we can use the above inequality and get

[ ns ] 2e_ke2/(2c2 )

Prob[IX -1 aCid> ~]= Prob ~=

5=1

Choose a suitable k = O(logn/e2), and the lemma follows. Note that the prob-

ability can be influenced by varying the size of the sample within a constant

factor. 9

12.3 Approximating Smooth Integer Programs

In this section we are going to prove Theorem 12.3 for quadratic programs, and

we will indicate how the idea can be generalized to degree d objective functions.

We only address the maximization version, minimization is similar.

12.3.1 The Quadratic Case

Theorem

12.10. Consider the following quadratic integer program

maximize xT Ax + bT x

subject to x = (Xl,...,xn) T E {0,1} n

and let A = (aij) be an (n x n) matrix with coefficients ai3 = O(1), b =

(bl,...,bn) T, bj = O(n), and let Opt denote the maximum value of the ob-

jective function.

There is an algorithm which for arbitrary ~ > 0 constructs a 0-1 vector y =

(Yl,..-,Yn) T for which

yTAy-4-bTy >/ Opt--~n 2.

y is computed in time n ~

12.3. Approximating Smooth Integer Programs 305

We describe a randomized algorithm that involves linear programming and the

sampling and rounding methods we have provided in the previous section. Later

on, in Section 12.3.2, we will sketch how the algorithm can be derandomized in

order to obtain a deterministic scheme. Throughout the proof we imitate the

approach we have already outlined for MAXCUT.

Proof.

The first step is to transform the quadratic program into a linear pro-

gram. Let

x* = (x~,... ,x*) T

be a solution that maximizes the value of the

objective function. Of course, we do not really know such a vector, we are just

about to demonstrate how such a vector or at least an approximate one can be

constructed. But to explain the idea of the algorithm and for its analysis, we

assume for the moment that we already know x*. We define

r T

-- (rl,...,

rn)

via

r T ~ x *T A + b T ,

that is,

ri = ~,j=l xj aji + bi,

the inner product of x* and the i-th column of A

plus

bi,

and obtain a new linear system

maximize

rT x

xTA q- b T = r T

(12.1)

x e {0,

1}'.

Clearly, x* is an optimal solution to this system.

Our preliminary goal now is to find an estimate vector

s = (sl,..., sn) T,

which

is a good approximation for r. s is allowed to differ from r in every coordinate

by a linear error

[ri - si[ <<. en

for l~<i~<n. (*)

Since we do not know a direct way to determine s without knowing x*, we

establish a set of candidate vectors for s, one of which is guaranteed to satisfy

(,). Like in MAXCUT we choose a (multi-)set Z of k = O(logn/s 2) indices by

random sampling. We process each of the 2 k possible 0-1 assignments for the

xj,

j E Z, as an outer loop for the algorithm and for each assignment we compute

a vector s given by

si = ~ Z aji xj + bi

for 1 ~< i ~< n.

jEZ

This yields a set S of 2 k candidate vectors for s. We know that one of the

assignments equals x* with respect to the drawn indices in Z

n ,

S 7 = ~ ~ajixj +bi

for

l<~i<<.n.

jEz

Since

is fixed and the

aji are

O(1), we can apply the Sampling Lemma to

~j e z aji x~ which ensures