Séminaire de Mathématiques Discrètes jeudi 12 mars - Guilherme D. da Fonseca

 

Numerous approximation algorithms for problems on geometric intersection graphs have been proposed in the literature, exhibiting a sharp trade-off between running times and approximation ratios. We introduce a method to obtain linear-time constant-factor approximation algorithms for such problems. To illustrate its applicability, we obtain results for three well-known optimization problems on two classes of geometric intersection graphs. Among such results, our method yields linear-time (4+epsilon)-approximations for the maximum-weight independent set and the minimum dominating set of unit disk graphs, thus bringing dramatic performance improvements when compared to previous algorithms that achieve the same approximation ratios.

Joint work with Vinicius G. Pereira de Sa and Celina M. H. de Figueiredo.