Comparison of the FR, IR and the Greedy Algorithms

We first compare our incremental rounding (IR) algorithm with the fixed rounding (FR) algorithm proposed in  [#!hochbaum!#] and with the greedy algorithm. The results are further compared with the lower bound obtained as the optimal solution from the LP method. The LP solver we used, is called PCx [#!pcx!#] which is an interior-point based linear programming package.

We use a simple setup to investigate the relative performance of these algorithms. The underlying network graph is a single graph of randomly distributed nodes on a 100 by 100 unit length map. The service range of a server is 20 units. Ideally, if nodes are perfectly positioned, this will give a solution of $\lceil{\frac{100}{40}}\rceil\times\lceil{\frac{100}{40}}\rceil = 9$ selected servers regardless of the node density. The lower bound we obtained is indeed not far from the ideal and stays constant with increasing node density as shown in Figure 5.1.

Figure 5.1: Performance Comparison of the FR and IR Algorithms

[Performance without the pruning routine] [width=0.45]figure/chap5/alg_no_prune_nodes.eps [Performance with the pruning routine] [width=0.45]figure/chap5/alg_prune_nodes.eps

We show the performance of the rounding algorithms with and without the pruning routine in Figure 5.1. As expected, the FR algorithm performs badly with increasing node density, since the largest number of sets covering a node $p$, also increases with node density which makes the selection criterion less strict. On the other hand, the IR algorithm is always the closest to the lower bound. The FR algorithm does benefit greatly from the pruning routine, achieving performance closer to the lower bound, and is only slightly worse than the IR algorithm, but better than the greedy algorithm. This relative performance holds for other settings we have tried as well. In the rest of the Chapter, we will mainly focus on the IR algorithm to evaluate the placement methods in more complicated network configurations.