X hits on this document

30 views

0 shares

0 downloads

0 comments

4 / 9

lem (PLP) and its dual packing problem (DLP) are linear

programs of the form

min s.t.

T

cx A·x b x0

max s.t.

bTy

AT

·y c y 0

where all entries of A, b, and c are non-negative. The dual LP of a covering LP is a packing LP and vice versa. We assume that all variables xi and yi represent some value in the graph, that is, they belong to some node or edge. We assume that the conditions of the LP are local in the sense t h a t w h e n e v e r a p r i m a l ( d u a l ) v a r i a b l e x i ( y j ) o c c u r s i n t h e i n e q u a l i t y c o r r e s p o n d i n g t o a d u a l ( p r i m a l ) v a r i a b l e y j ( x i ) , x i a n d y j a r e s e p a r a t e d b y a t m o s t a c o n s t a n t n u m b e hops in the network graph. This locality condition is true in all natural network coordination problems such as minimum dominating set (MDS), maximum matching (MM), etc. In MDS, for each nodes vi there is a primal variable xi and a dual variable yi. The primal feasibility condition demands that the sum of the x-values in the 1-neighborhood of all nodes is at least 1, the dual feasibility condition states that the sum of the y-values of each 1-neighborhood is a most 1. Hence, only variables of adjacent nodes occur together in an inequality of the MDS LP. For MM, x-variables are associated with nodes and y-variables correspond to edges. Again, only adjacent variables occur together in the same inequality. r o f

We will now first look at a solution of such LPs based on the network decomposition of Section 3. We will then show, how to convert this into a solution which does not need global coordinates using the idea of averaging over the set of all possible solutions.

Assume that we are given a (1, O(1))-decomposition as described in Section 3. By exchanging the IDs among direct neighbors, each cluster can select the node with the largest ID as leader. In parallel, each leader then computes a local LP such that the combined local solutions form a constant approximation for (PLP) or (DLP). Let v0 be the leader of s o m e c l u s t e r C 0 . L e t Y 0 b e t h e s e t o f a l l d u a l y - v a r i a b l which belong to nodes at distance at most 1 from v0 or to e s e d g e s w h i c h a r e a d j a c e n t t o n e i g h b o r s o f v 0 . T h e s e t Y 0 h a s a c o r r e s p o n d i n g s e t E 0 o f p r i m a l i n e q u a l i t i e s o f ( P L P ) . L e t X 0 b e t h e s e t o f p r i m a l x - v a r i a b l e s w h i c h o c c u r i n t h e i n e q u a l i t i e s E 0 . L e t P 0 b e t h e c o v e r i n g p r o b l e m s c o n s i s t i n g o f t h e o b j e c t i v e f u n c t i o n o f ( P L P ) a n d t h e i n e q u a l i t i e s E 0 . P 0 i s a L P o n t h e v a r i a b l e s X 0 . F u r t h e r , packing LP which is obtained by deleting all variables from l e t D 0 b e t h e ( D L P ) w h i c h a r e n o t i n Y 0 . T h a t i s , w e r e s t r i c t t h e m a t r i x A t o t h e r o w s a n d c o l u m n s d e fi n e d b y Y 0 a n d X 0 , By the definition of (PLP) and (DLP), the nodes and edges of the variables in X and Y are all within constant distance r e s p e c t i v e l y . f r o m v 0 . T h u s , v 0 c a n l o c a l l y s o l v e P 0 a n number of rounds. The local solutions for each cluster can be combined by summing up the values of all local LPs for each variable. d D 0 i n a c o n s t a n t

Lemma 4.1. Summing up the described local LPs for all clusters yields solutions for PLP) and DLP) with the same value of the objective function. The solution of PLP) is a feasible constant approximation, the solution of DLP) can be made feasible by dividing each y-variable by a constant factor.

Proof We start by proving the feasibility of (PLP). Be- cause all clusters have diameter 1, all dual y-variables are in t h e s e t Y i o f a t l e a s t o n e c l u s t e r l e a d e r v i . T h e r e f o r e , e v e r y i n e q u a l i t y o f ( P L P ) o c c u r s i n s o m e l o c a l L P P i . B e c a u s e t x-values of all local LPs are summed up, it is sufficient to make every primal covering constraint feasible once in order to obtain a globally feasible solution for (PLP). h e

For the almost-feasibility of (DLP), observe that we have c h o s e n t h e s e t Y 0 s u c h t h a t t h e s o l u t i o n o f t h e l o c a l d u a problem D0 is feasible for (DLP) (set all unused y-variables to 0): Clearly all inequalities which appear in D0 are also feasible for (DLP); because all inequalities of (DLP) contain- l i n g a v a r i a b l e y i Y 0 a l s o a p p e a r i n D 0 , a l l o t h e r i n e q u a l ties of (DLP) are of the form 0 cj for some j. Because of i - t h e l o c a l i t y c o n d i t i o n f o r o u r L P s , a l l x i X 0 a r e a t a c stant distance from v0. Therefore, each xi can only occur in a constant number of local covering LPs. Because there is a one-to-one correspondence between primal variables and dual inequalities, each dual inequality can as well only occur in a constant number of local LPs. Because each local LP is dual-feasible for (DLP), this means the the sum of all local LPs is dual feasible for (DLP) up to a constant factor. o n -

If all local LPs are solved optimally, the values of the o b j e c t i v e f u n c t i o n s f o r a p a i r ( P 0 , D 0 ) o f l o c a l L P s a r e e q u a l Therefore, clearly, when summing up the local LPs, we get the same objective function values for (PLP) and (DLP) as well. By LP duality, the approximation factor of (PLP) is at most equal to the constant factor by which the dual inequalities have to be divided in order to obtain a feasible (DLP) solution. .

We will now show, how to average the described solution over all possible coordinate systems. Equivalently to aver- aging the x and y values for all possible coordinate systems, we can choose one coordinate system uniformly at random2 and compute the expected values for the x and y variables. In the above description, we have chosen the local LPs such that they are independent of the nodes’ assignments to clus- ters. They only depend on the choice of the cluster leaders. Hence, each node vi can compute its local LP. Let pi be the probability that vi is a cluster leader if the coordinate system is chosen uniformly at random. If we assume that every node vi can compute its pi, a constant-factor approx- imation to a given covering or packing LP can be computed as follows.

1. compute local LP and pi

2 . i n c r e a s e a l l v a r i a b l e s x j o r y j o f L P b y p i x j o r respectively p i y j ,

3. if LP is a packing problem, divide by appropriate con- stant factor

It remains to show that pi can really be computed. We will present an elegant way to approximate pi up to a small constant factor. By the construction of the network decom- position of Section 3, pi is the probability that vi is the node with the largest ID within its cell of a random square grid of cell size 1/2. Hence, pi is the probability that vi has the largest ID in a random square or side length 1/2 con- taining vi. Because for every square of side length 1/2,

2In principle, this means that the origin and the direction of the x-axis are chosen uniformly at random

Document info
Document views30
Page views30
Page last viewedFri Dec 09 18:41:46 UTC 2016
Pages9
Paragraphs361
Words10583

Comments