X hits on this document

# On the Locality of Bounded Growth - page 5 / 9

20 views

0 shares

5 / 9

1

1/(2 2)

F i g u r e 2 : C o m p u t a t i o n o f p i : N o d e v i i s a t t h e c e n - ter, the encircled nodes are the neighbors of vi hav- ing a larger ID than vi. The shaded area is propor- t i o n a l t o p i .

there is a circle of diameter 1/2 which is completely inside t h e s q u a r e , t h e p r o b a b i l i t y p i o f h a v i n g t h e l a r g e s t I D i n a r a n d o m c i r c l e o f d i a m e t e r 1 / 2 i s p i p i . U s i n g p i i of pi in the above algorithm therefore guarantees that the computed (PLP) solution is feasible. n s t e a d

We will now argue that the objective functions are not a ff e c t e d t o o m u c h b y u s i n g p i i n s t e a d o f p i . L e t p i probability that vi is the node with largest ID in a square of b e t h e s i d e l e n g t h 1 / 2 c o n t a i n i n g v i . T a k i n g p i i n s t e a d responds to making the network decomposition with a grid o f p i c o r - o f c e l l s i z e 1 / 2 i n s t e a d o f 1 / 2 . U s i n g p i i n t h rithm would therefore give a solution which is at most by a factor 2 worse than the solution when using pi because the area of each cell is smaller by a factor 2. Hence, the num- ber of neighboring clusters in the decomposition doubles. e a b o v e a l g o - A d d i t i o n a l l y , w e h a v e t h a t p i p i b e c a diameter 1/2 completely contains a square with side length u s e e v e r y c i r c l e o f 1 / 2 . T h u s , t a k i n g p i i n s t e a d o f p i i n t h e results in a feasible solution for (PLP) which is worse than d e s c r i b e d a l g o r i t h m t h e s o l u t i o n u s i n g p i b y a t m o s t a f a c t o r 2 . T h e p r o b a b i l i t y p i c a n b e c o m p u t e d b y v i a s f o l l o w s .

• 1.

exchange 1-hop distances with neighbors

• 2.

• 3.

geometrically arrange neighbors in one possible way.

4. For some node v, let D(v) be the disk with radius 1/(22) around v. Further, let N+(v) be the set of neighbors of v which have a larger ID than v. The p r o b a b i l i t y p i c a n b e c o m p u t e d a s t h e a r e a o f

D(vi) \

[

# D(u)

uN

(v

)

d i v i d e d b y t h e a r e a o f D ( v i ) . T h a t i s , p i i s t h e f r a c t i o n of D(vi) which is not covered by any of the disks D(u) with ID(u) > ID(vi).

Figure 2 illustrates step 4 of the described algorithm.

Lemma 4.2. The above algorithm correctly computes the p r o b a b i l i t y p i t h a t v i i s t h e n o d e w i t h t h e l a r g e s t I D i random circle of diameter 1/2 containing vi. n a

Proof We first assume that step 3 of the algorithm is unique, that is, we have a local coordinate system where vi and its neighbors are correctly geometrically arranged. Choosing a random circle of diameter 1/2 containing vi can be done by placing the center of the circle uniformly at random in the disk of radius 1/(22) around vi. For a given center p, vi has the largest ID if there is no node vj with ID(vj ) > ID(vi) at distance at most 1/(22) from p. Therefore, vi does have the largest ID if and only if the center p is chosen at distance more than one from all neighbors vj of vi with ID(vj ) > ID(vi). This exactly is the case if p is in the area which is computed in step 4 of the algorithm. Hence, the lemma is true if step 3 is unique.

Let N(vi) be the induced graph of vi’s neighbors (not in- cluding vi), that is, the edges of N(vi) are all edges between neighbors of vi. We start with the case where N(vi) consists of a single component. If we know the distances to two ad- jacent neighbors as well as the distance between those two neighbors, we can compute the angle at vi between the two neighbors. If N(vi) is a single component, we can then find the angles between all neighbors of vi. The geometry of the 1-neighborhood of vi is therefore determined up to rotation around vi, that is, we can compute a local coordinate system for which step 3 of the algorithm is unique.

Step 3 of the algorithm is not unique if N(vi) consists of several connected components. The geometry of each component can be determined, however the angle between differenct components can not be infered from the knowl- edge of the distances between neighbors alone. However, two nodes from different components of N(vi) are at dis- tance more than 1 from each other. Therefore, the disks of radius 1/(22) around two nodes u, uN(vi) do not in- tersect if u and ubelong to different components in N(vi). Thus, the area which is computed in step 4 is the same for all possible geometric arrangments of the neighbors of vi.

The results of this section are summarized in the upcom- ing theorem. The time bound for the fractional dominating set problem follows because in this case the given algorithm becomes particularly simple. The local LPs can be solved in this case by assigning 1 to all cluster leaders and 0 to all o t h e r n o d e s . T h u s , t h e v a l u e s p i f o r m a c o n s t a n t a p p r o x mation for minimum fractional dominating set. i -

Theorem 4.3. In the given UDG model where distances are known, all local fractional covering and packing prob- lems can be approximated up to a constant factor in constant time. In particular, the fractional minimum dominating set problem can be approximated in a single round.

From a complexity theoretic point of view, looking at frac- tional distributed problems is extremely interesting. On the one hand, they usually still have the main properties of their corresponding integer problems, on the other hand, some of the synchronization problems occuring for the integer vari- ants of the problems can be avoided. However, with some exceptions [7], in practice we are mostly interested in in- teger solutions. In the case of covering and packing prob- lems, randomized rounding can be used in order to convert fractional solutions into reasonable approximations for the integer problems [25]. In [18, 16], an efficient distributed formulation of randomized rounding is given.

To conclude this section, we would like to highlight an in- triguing comparison concerning the distributed complexity

 Document views 20 Page views 20 Page last viewed Mon Oct 24 14:54:35 UTC 2016 Pages 9 Paragraphs 361 Words 10583