Linear-Time Approximation Algorithms for Unit Disk Graphs
Guilherme Dias da Fonseca, Vinícius G. Pereira de Sá, Celina M.H. de Figueiredo · arXiv (Cornell University) · 2014
Numerous approximation algorithms for unit disk graphs have been proposed in the literature, exhibiting sharp trade-offs between running times and approximation ratios. We propose a method to obtain linear-time approximation algorithms for unit disk graph problems. Our method yields linear-time (4 + ε)-approximations to the maximum-weight independent set and the minimum dominating set, as well as a linear-time approximation scheme for the minimum vertex cover, improving upon all known linear- or near-linear-time algorithms for these problems. 1