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 v_{i }hav- ing a larger ID than v_{i}. 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 p_{i }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 v_{i }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 p_{i }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.

compute angles between adjacent neighbors

3.

geometrically arrange neighbors in one possible way.

4. For some node v, let D(v) be the disk with radius 1/(2^{√}2) 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(v_{i}) \

[

# D(u)

u∈N

(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(v_{i}) which is not covered by any of the disks D(u) with ID(u) > ID(v_{i}).

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 v_{i}. n a

Proof We first assume that step 3 of the algorithm is unique, that is, we have a local coordinate system where v_{i }and its neighbors are correctly geometrically arranged. Choosing a random circle of diameter 1/^{√}2 containing v_{i }can be done by placing the center of the circle uniformly at random in the disk of radius 1/(2^{√}2) around v_{i}. For a given center p, v_{i }has the largest ID if there is no node v_{j }with ID(v_{j }) > ID(v_{i}) at distance at most 1/(2^{√}2) from p. Therefore, v_{i }does have the largest ID if and only if the center p is chosen at distance more than one from all neighbors v_{j }of v_{i }with ID(v_{j }) > ID(v_{i}). 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(v_{i}) be the induced graph of v_{i}’s neighbors (not in- cluding v_{i}), that is, the edges of N(v_{i}) are all edges between neighbors of v_{i}. We start with the case where N(v_{i}) 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 v_{i }between the two neighbors. If N(v_{i}) is a single component, we can then find the angles between all neighbors of v_{i}. The geometry of the 1-neighborhood of v_{i }is therefore determined up to rotation around v_{i}, 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(v_{i}) 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(v_{i}) are at dis- tance more than 1 from each other. Therefore, the disks of radius 1/(2^{√}2) around two nodes u, u^{ }∈ N(v_{i}) do not in- tersect if u and u^{ }belong to different components in N(v_{i}). Thus, the area which is computed in step 4 is the same for all possible geometric arrangments of the neighbors of v_{i}.

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