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

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

306 Chapter 12. Dense Instances of Hard Optimization Problems

say, with probability at least 1 - 2 n -2 for one constraint i, respectively with

probability at least 1 - 2 n-1 for all n sums.

Let us pause here and recapitulate the proof up to this point. We have obtained

a set of vectors S and know that this set contains a certain vector s, namely s*,

which with high probability approximates r within the required accuracy. All

this was done without actually involving x* in the computation. The remainder

of the algorithm is executed for each of the candidate vectors in S. Eventually, we

take the one with the best result, i.e., the largest value of the objective function.

For the analysis let us concentrate on that vector s which satisfies (.).

Look at the following program

maximize

sTx

(12.2)

xT A + b T >/(Sl-~n,...,sn-cn)

xTA+b T <<.

(Sl+en,...,sn+en)

x e {0, i} n

(Here the inequalities are supposed to hold for every coordinate of a vector.) x*

is a feasible 0-1 solution to the above system, and

8Tx * -~

rTx * -- (r T --

sT)x *

= x'TAx * + bTx * -- (r T -- 8T)x * >1

Opt--En 2 .

If we relax the integrality condition and replace it by x E [0, 1] n, we can use

linear programming and find an optimal fractional solution x in polynomial time.

Because of the relaxation we have

sTx >1 sTx *.

Then we apply the rounding

procedure we saw in Lemma 12.8. The resulting 0-1 vector y satisfies

yTA+bT >1 (8,--r

with high probability. The value of

sTy

can be bounded from below with the

help of the following inequality

sTy >1 sTx--O(nx/nlogn)

8rz

>/ Opt-r

2 - O(nv~logn ) .

Define an error vector 6 via

(~T =

xTA+b w _s T.

As for each coordinate 16il ~< ~n

holds, we get

[STyl <~ e n 2.

Finally, let us combine the inequalities in order to bound the possible deviation

from the value of the objective function of the original program.

12.3. Approximating Smooth Integer Programs 307

yT Ay W bTy = (yT A T bT)y

= (yTA q- b T - (xTA -4- bT))y -4- ~Ty -4- sTy

(o t

= Opt -- (2c+o(1)) n 2

The running time of the algorithm is dominated by solving linear programs and

subsequent randomized rounding of the solution vectors which can be done in

polynomial time. This is repeated for every possible 0-1 assignment to the sam-

pled indices, that is 2 k -- 20(l~ -- n O(1/e2) times. The algorithm outputs

the vector with the largest value of the objective function. 9

Remark 12.11. The error caused by the sampling is significantly larger than

the error produced by randomized rounding. So if the sampling could be replaced

by a better method, this would improve the approximation guarantee.

12.3.2

Derandomization and Generalization of the Scheme

In the proof for the quadratic case we demonstrated how a quadratic program is

converted into a program with a linear objective function and linear constraints

(see (12.1) and (12.2)). In the same fashion, we can express the optimum of a

degree d polynomial with the help of degree d- 1 polynomials. Again by random

sampling we recursively transform these constraints into constraints of a lower

degree, ending up with a system of linear constraints. Theorem 12.3 is obtained

by an induction on the degree. An immediate consequence is that the same

algorithm works if the original program has smooth degree d - 1 constraints.

The following generalization holds.

Corollary 12.12.

Consider a given smooth degree d integer program which is,

in addition, subject to a polynomial number of constraints

qj(xl,...,xn) <<. bj,

each qj being a smooth polynomial of degree dj < d. Then, for each c > O, the

algorithm constructs a 0-1 solution vector y within an additive error of ~ n d of

the optimum, and satisfies

qj(Yl,...,Yn) <<. bj+en d~.

So far, we have only described a randomized scheme. A deterministic proce-

dure can be derived by derandomizing the rounding algorithm and the sampling

procedure.

Raghavan [Rag88] coined the term "method of conditional probabilities" for the

derandomization of randomized rounding. A detailed description of the method

of conditional probabilities is presented in Chapter 3.

308 Chapter 12. Dense Instances of Hard Optimization Problems

Derandomizations of the Sampling Lemma are published in [BGG93] and in

[BR94]. Gillman [Gil93] shows that choosing O(log

n/~ 2)

indices independently

can be simulated by taking the indices reached along a random walk of length

O(logn/e 2) on an expander graph with constant expansion and bounded de-

gree. Because of the bounded degree, there are only

n ~

different random

walks. So it remains polynomial, even if we process the algorithm for all samples

produced from these random walks and take the best result.

12.4 Polynomial Time Approximation Schemes for Dense

MAXCUT and MAXEkSAT Problems

In this section we will apply the approximation procedure developed in Sec-

tion 12.3 and realize that it turns out to be a PTAS on dense MAXCUT and

MAxEkSAT instances. Notice that for both problems exact optimization remains

Af:P-hard when we restrict ourselves to dense instances.

To understand this for MAXCUT, we reduce a general graph to a dense graph by

adding a complete bipartite graph on 2n vertices. The resulting graph is dense

because the average degree is linear in the size of the graph. The initial graph

has a cut of at least k edges if and only if the dense graph has a cut of at least

k + n 2 edges.

A reduction from MAxEkSAT to the dense MAXEkSAT problem is performed

by adding dummy clauses that are always satisfied, regardless of the assignment

to the Boolean variables.

12.4.1 MAXCUT

We have already given a smooth quadratic formulation for MAXCUT. By The-

orem 12.3 for a and ~ > 0, we can compute an assignment to the variables, in

n ~

steps, such that the size c of the cut satisfies

E~ n 2

c >/ Opt - -~- .

For a dense graph, having a n 2 edges, one can randomly produce a cut with

expected cutsize E[Cut] of at least

a n2/2

edges by putting each vertex on the

left or on the right side with probability 1/2.

1 1

E[Cut] = Eer~ = ~[E[ /> ~an 2

e~:E

This implies Opt >/o~n2/2. Summarizing, we have

12.4. MAXCUT and MAxEkSAT 309

~0~ 2

c /> Opt--~n

/> Opt-eOpt = (l-e) Opt.

In a similar way one can devise a formulation for MAXDICUT as a smooth

quadratic program and achieve a PTAS for dense directed graphs. We are not

going to elaborate on this further. The reader who is interested in approximation

algorithms for general MAXCUT problems is directed to Chapter 11. Semidef-

inite programming tools and randomized rounding axe applied to a relaxation

of MAXCUT. For recent non-approximability results concerning MAXCUT and

MAXDICUT see Chapter 8.

12.4.2 MAXEkSAT

Let us now consider a dense EkSAT formula with Boolean variables yl,..., Yn

and

m >~ a n k

clauses. For each Boolean variable

we introduce a 0-1 variable

xi (i = 1,..., n),

Then we transform each positive literal

into 1 -

and each

negative literal ~-~ into

xj.

The Boolean operator V is replaced by the integer

multiplication and for the whole clause we get the final expression by subtracting

the product from 1.

For instance: y--~

V Y2 V

Y3 ----+

1-xl(1-x2)(1-xa).

A satisfying Boolean assignment to the y-variables of a clause corresponds to a

0-1 assignment to the x-variables that evaluates to 1. True is translated into 1,

false into 0.

Denote the resulting term of the j-th clause by

pj(xl,..., x,~).

We have turned

the original kSAT formula into the following smooth degree k program.

~Tt

maximize ~ pj(xl,...,

xn)

j----1

subject to

xiE{0,1)

for l~<i~<n.

Let Opt be the maximum number of clauses of the formula any Boolean as-

signment can satisfy and let t be the number of satisfied clauses the algorithm

produces. For a random true/false assignment a clause of length k is false with

probability 2 -k, true with probability 1 - 2 -k. So we deduce

Opt

/> (1-2-k)m >/ (1-2-~)czn k.

For ~ > 0, in time

n O(2:~/(e a)2),

the scheme produces a solution with

_ ~ a nk

(1 -- ~ 1

t >/ Opt >t Opt

2--s 1) / >/ (1- ~)Opt

true clauses.

310 Chapter 12. Dense Instances of Hard Optimization Problems

12.5 Related Work

Apart from the approximation schemes for the problems we have presented here,

Arora, Karger and Karpinski have designed PTASs for GRAPHBISECTION of

everywhere dense graphs and for DENSESTSUBGRAPH, as well as an exact al-

gorithm for 3-COLORING of 3-colorable graphs. (This will be considered in the

Exercises). They also generalize the notion of density to MAX-SNP problems,

representing them as MAX-k-FUNCTIONSAT instances for a suitable k, which

depends on the special problem, and obtain similar PTASs as in Section 12.4.2

for the resulting instances, if they are dense. In MAX-k-FUNCTIONSAT the input

consists of m Boolean functions in n variables, each function depending only on

k variables. The objective is to assign truth values to the variables so as to sat-

isfy the maximum possible number of these functions. An instance is dense, if it

consists of

f~(n k)

functions. (For the connection to MAX-SNP see also [Pap94].)

Fernandez de la Vega [Fer96] has devised randomized approximation schemes for

MAXCUT and MAXACYCLICSUBGRAPH. In his placement procedure he applies

sampling techniques to obtain a subset W of the vertices, which completely

belongs to one side of the maximum cut. The remaining vertices are allocated

according to their adjacency relations to W. The running time of the algorithm

is 0(21/~2+~ n2).

A paper by Arora, Frieze and Kaplan [AFK96] deals with assignment problems

with additional linear constraints. They present a new rounding procedure for

fractional bipartite perfect matchings, different from the Raghavan-Thompson

rounding method described in Lemma 12.8. Here, the variables are not rounded

independently. They give an additive approximation algorithm for the smooth

QUADRATICASSIGNMENTPROBLEM, which uses random sampling to reduce the

degree by one. The algorithm is similar to the presented scheme, except for

the new rounding technique. The running time of the algorithm is only quasi-

. 2 .

polynom,al: n ~176

n/~ ),

but they give PTASs for dense instances of MINLINEAR-

ARRANGEMENT, MAXACYCLICSUBGRAPH and several other problems.

Karpinski and Zelikovsky [KZ97] study STEINERTREE problems where each ter-

minal must be adjacent to fl(n) non-terminal vertices and give a PTAS for this

situation. For the SETCOVER problem, they call an instance with a family of

m subsets of a set of n elements e-dense, if each element belongs to r m sub-

sets. They show that SETCOVER on dense instances is not AlP-hard, unless

JV'P C_ DTIME(

n l~

), and provide a greedy algorithm with approximation ra-

tio c log n for every c > 0. Open questions are whether there is a constant-factor

approximation or even an exact polynomial time algorithm for dense SETCOVER

and whether the dense STEINERTREE problem is in 7 ~.

12.5. Related Work 311

Exercises

The results discussed in the exercises are due to Arora, Karger and Karpinski.

(See [AKK95b].)

Exercise

12.1. GRAPHBISECTION

Instance:

Given an undirected graph G = (V, E) with 2n vertices.

Problem: Partition the vertex set into two disjoint subsets 111 and V2 of size

n such that the number of edges having one endpoint in 111 and the

other endpoint in V2 is minimized.

Show that the existence of a PTAS for dense instances of the GRAPHBISECTION

problem implies the existence of a PTAS on general instances.

Exercise

12.2.

DENSESTSUBGRAPH

Instance: Given an undirected graph G -- (V, E) and a positive integer k.

Problem: Determine a subset V ~ of the vertices, IV'I - k, such that the graph

G ~ = (V ~, E(V*))

has the most edges among all induced subgraphs

on k vertices.

Construct a PTAS for

DENSESTSUBGRAPH on

everywhere dense graphs for k --

Exercise 12.3. Sketch a randomized polynomial algorithm for 3-COLORING of

everywhere dense 3-colorable graphs based on a random sampling approach.

(Hint: If the random sample is large enough, one can show that with high

probability every vertex has a sampled neighbor. How can this observation be

used to extend a proper coloring of the sample to a coloring of the whole vertex

set?)

13. Polynomial Time Approximation Schemes

for Geometric Optimization Problems in

Euclidean Metric Spaces

Richard Mayr, Annette Schelten

13.1 Introduction

Many geometric optimization problems which are interesting and important in

practice have been shown to be AfT~-hard. However, for some cases it is possible

to compute approximate solutions in polynomial time.

This chapter describes approaches to find polynomial time algorithms that com-

pute approximate solutions to various geometric optimization problems in Eu-

clidean metric spaces. It is mainly based on the recent work of Arora [Aro97],

which significantly improved previous works by Arora [Aro96] and Mitchell

[Mit96]. First let us define the problems we will consider:

TRAVELING SALESMAN PROBLEM (TsP)

Instance:

A graph G = (V, E) on n nodes with edge weights defined by c :

E ~

Problem: Find a cycle in G with IV] = n edges that contains all nodes and has

minimal cost.

Such a cycle is called the salesman tour for G. A variant of this problem is k-

TsP where for a given k < n the aim is to find the k vertices with the shortest

traveling salesman tour, together with this tour. Both problems are J~fT~-hard.

In practice the graph is often embedded in the Euclidean space ~a with di-

mension d C IN. If additionally the distances are given by the Euclidean norm

(/2-norm) we speak of Euclidean TsP:

EUCLIDEAN TsP

Instance:

A graph G = (V, E) in ]~a on n nodes with edge weights defined by

the Euclidean norm.

Problem: Find a cycle in G with IV I = n edges that contains all nodes and has

minimal cost.

Since the distances between the nodes are given by a norm, we are in particular

dealing with complete graphs. The more general case that the graph lies in an

arbitrary metric space is called metric TsP.

314 Chapter 13. Approximation Schemes for Geometric Problems

It has long been known that TsP is A/P-hard [Kar72]. Later it was shown that

this even holds for the special case of Euclidean TsP [Pap77, GGJ76]. While -

under the assumption that P ~ A/P - metric TsP and many other problems

do not have a polynomial time approximation scheme (proved by Arora, Lund,

Motwani, Sudan and Szegedy [ALM+92]), there is a polynomial time approxi-

mation scheme (PTAS) for Euclidean TsP.

In the following we will describe such a PTAS where the graph lies in the Eu-

clidean space I~ ~ . It can be generalized to the d-dimensional Euclidean space •d,

as well as to other related problems (see Section 13.5).

Arora's [Aro97] new algorithm is a randomized PTAS, which finds a (1 + 89

approximation to Euclidean TsP in time

O(n(logn) ~

where c > 0 and n

denotes the number of given nodes. In earlier papers Arora [Aro96] and Mitchell

[Mit96] independently obtained PTAS that need

O(n ~

time.

Quoting the author, the main idea of the PTAS relies "on the fact that the plane

can be recursively partitioned such that some (1 + ~)-approximate salesman tour

crosses each line of the partition at most t =

O(clogn)

times. Such a tour can

be found by dynamic programming." [Aro97].

13.2 Definitions and Notations

In the following we use the convention that rectangles are axis-aligned. The

size

of a rectangle is the length of its longer edge. For a given set of n nodes the

bounding box

is the smallest square enclosing them. We will always denote the

size of any bounding box by L and without loss of generality let L E N.

In the following we assume that there is a grid of granularity 1, such that all nodes

lie on grid points. Moreover, we assume that the bounding box has size

L = nc.

This is no restriction, since any instance of the problem can be transformed

into one that satisfies these conditions with small extra cost: Place a grid of

granularity

L/(nc)

over the instance and move every node to the nearest grid

point. (It is possible that two nodes now lie on the same grid point.) If we find

a solution for this new instance, then we also have a solution for the original

instance. Let p be a salesman path for the new instance. We can construct a

salesman path p~ for the original instance as follows: For every node add two

edges, from the node to the nearest grid point and back. The total length of

these additional edges is ~< 2n. V~/2-

L/(nc).

As the length Opt of the optimal

tour is at least L, this is ~< V~ Opt/c

O(Opt/c). This additional cost is

acceptable, since we are only interested in (1 + 1/c)-approximations. So far the

minimal internode distance in the new instance is

L/(nc).

Now we scale all

distances by

L/(nc)

and obtain a minimal internode distance of 1. The new size

of the bounding box is now

nc.

The transformation only requires

O(n

log n) time.

13.2. Definitions and Notations 315

The definitions of a dissection and a quadtree are essential to this PTAS. Both

are recursive partitionings of the bounding box into smaller squares. To get a

dissection of the bounding box we partition any square into four squares of equal

size until each square has length at most 1. These four squares are called the

children of the bigger one. Similarly we define a quadtree. Also this time each

square is divided into four equal squares, but we already stop when a square

contains at most one node.

Instead of "normal" dissections or quadtrees we will consider shifted ones. For

a, b E N the (a, b)-shift of the dissection is obtained by shifting all x- and y-

coordinates of all lines by a and b respectively, and then reducing them modulo

L. This can lead to cases where previous rectangles are now wrapped around.

Consider a simple dissection of depth one. There is only the bounding box and its

four children. If it is shifted by shifts a, b ~ L/2, then three of the original chil-

dren will be wrapped around. The only child that is not wrapped around is the

child-square that used to reside in the lower left corner; it is now approximately

in the center of the bounding box.

Let there be a shifted dissection. To construct the corresponding quadtree with

shift (a, b) we cut off the partitioning at each square that contains at most one

node.

In a dissection or in a quadtree a child-square has exactly half the size of its

parent-square (the size is defined as the length of the longer edge). The size

of the bounding box is nc and c is a constant, thus at a depth of O(logn) the

rectangles in the quadtree have size 1. As the minimal internode distance is 1, the

construction stops there, because there is at most one node in the square. Thus

any quadtree - shifted or not - has depth O(logn) and consists of O(number

of nodes 9 depth) = O(n log n) squares. Hence the quadtree can be obtained in

time O(n log 2 n).

Finally we define the concept of a light salesman tour, which is crucial for the

following.

Definition 13.1. Let m, t E N. For each square we introduce an additional node

at each corner and m further equally-spaced nodes on each of its ]our edges. These

points are called portals.

We say that a salesman tour is (m, t)-light with respect to the shifted dissection

if it crosses each edge of each square in the dissection at most t times and all

crossings go through one of the portals. A tour can use a portal more than once.

To find a nearly optimal salesman tour by dynamic programming means to

find an approximate tour in each subsquare and to put these tours together.

Therefore we have to consider all possibilities where a segment of a tour can

enter a square. In a (m, t)-light salesman tour these points are limited by the

discrete set of portals. Since the distances are given by the Euclidean norm, the

316 Chapter 13. Approximation Schemes for Geometric Problems

triangle-inequality holds, which means that the direct way between two nodes is

always at most as long as the way through an additional point. Hence removing

these additional points (portals) never increases the cost of the tour.

13.3 The Structure Theorem and Its Proof

The algorithm, which we will describe in Section 13.4, mainly relies on the fol-

lowing Structure Theorem:

Theorem 13.2. (Structure Theorem) Consider an Euclidean TsP instance with

bounding box of size L and the corresponding dissection with shift (a, b) where

a, b E N with 0 <~ a, b <~ L are picked randomly (every choice of a, b has the same

probability).

Then with probability at least 1/2 this dissection has a salesman tour of cost at

most (1 + 1/c)Opt that is (m,t)-light where m = O(c log L), t = O(c) and

m >/tlogL.

In the proof of this theorem we assume that we have an optimal tour p and

randomly chosen shifts a, b E N. Then we modify this tour until we get a new

approximate salesman tour - probably through additional nodes - in the dis-

section with shift (a, b) which is (m, t)-light. The following lemma helps us to

reduce the number of crossings between the salesman tour and the edges of each

square.

Lemma 13.3. (Patching Lemma) Let p be a closed path. Consider a line seg-

ment S of length I and assume that p crosses S at least three times. Then there

exist line segments on S of total length less than or equal to 61 such that the

addition of these segments to p changes p into a closed path p' of length IPl + 61

that crosses S at most twice.

Proof. We assume that p (of length IPl) is a closed path that crosses S 2k +

2 (2k + 1, respectively) times. Let Xl,...,x2k+2 (xl,...,x2k+l, resp.) be the

corresponding crossing points. For i -- 1,..., 2k break the path p at the points

xi. This implies that p breaks into 2k subpaths P1,-.., P2k. Also we double all

these points xi, i = 1,...,2k and call these copies x~. Now we are adding the

line segments of a minimal cost salesman tour through Xl,..., X2k, a minimal

cost salesman tour through x 1' ,..., x2 k, and also the line segments of minimal

cost perfect matchings among xl, X2k and among x~,. x ' All added line

"''' "'' 2k"

segments are lying on S which yields an Eulerian graph and hence there is a tour

p~ through xl,..., X2k+2, x~,..., x~k+2 using these line segments and the paths

P1,..., P2k. (An Eulerian graph is a connected graph which has a tour through

all edges. These graphs are characterized by the fact that they are connected and