Improved approximation algorithms for single-tiered relay placement

We consider the problem of Single-Tiered Relay Placement with Basestations, which takes as input a set \(S\) of sensors and a set \(B\) of basestations described as points in a normed space \((M,d)\), and real numbers \(0< r\le R\). The objective is to place a minimum cardinality set \(Q\) of wireless relay nodes that connects \(S\) and \(B\) according to the following rules. The sensors in \(S\) can communicate within distance \(r\), relay nodes in \(Q\) can communicate within distance \(R\), and basestations are considered to have an infinite broadcast range. Together the sets \(S, B\), and \(Q\) induce an undirected graph \(G=(V,E)\) defined as follows: \(V=S\cup B\cup Q\) and \(E=\{uv|u,v\in B\}\cup \{uv|u\in Q\) and \(v\in Q\cup B\) and \(d(u,v)\le R\} \cup \{uv|u\in S\) and \(v\in S\cup Q\cup B\) and \(d(u,v)\le r\}\). Then \(Q\) connects \(S\) and \(B\) when this induced graph is connected. In the case of the two-dimensional Euclidean plane, we get a \((1+\ln 6+\epsilon )<2.8\)-approximation algorithm, improving the previous best ratio of 3.11. Let \(\varDelta \) be the maximum number of points on a unit ball with pairwise distance strictly bigger than 1. Under certain assumptions, we have a \(\left( 1+\ln (\varDelta +1)+\epsilon \right) \)-approximation algorithm. When biconnectivity is required, we show that a variant of our previously proposed algorithm has approximation ratio of \(\varDelta + 2\). In the case of the two-dimensional Euclidean plane, our ratio of 7 improves our previous bound of 16.