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

programs of the form

min s.t.

# T

cx A·x ≥ b x≥0

max s.t.

b^{T}y

A^{T }

·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 x_{i }and y_{i }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 v_{i }there is a primal variable x_{i }and a dual variable y_{i}. 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 v_{0 }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 v_{0 }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 D_{0 }is feasible for (DLP) (set all unused y-variables to 0): Clearly all inequalities which appear in D_{0 }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 ≤ c_{j }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 v_{0}. Therefore, each x_{i }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 random^{2 }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 v_{i }can compute its local LP. Let p_{i }be the probability that v_{i }is a cluster leader if the coordinate system is chosen uniformly at random. If we assume that every node v_{i }can compute its p_{i}, a constant-factor approx- imation to a given covering or packing LP can be computed as follows.

1. compute local LP and p_{i }

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 p_{i }can really be computed. We will present an elegant way to approximate p_{i }up to a small constant factor. By the construction of the network decom- position of Section 3, p_{i }is the probability that v_{i }is the node with the largest ID within its cell of a random square grid of cell size 1/^{√}2. Hence, p_{i }is the probability that v_{i }has the largest ID in a random square or side length 1/^{√}2 con- taining v_{i}. Because for every square of side length 1/^{√}2,

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