Aller au menu Aller au contenu
Nos 6 domaines de compétences
Laboratoire des Sciences pour la Conception, l'Optimisation et la Production de Grenoble
Nos 6 domaines de compétences
Nos 6 domaines de compétences

> GSCOP_Recherche

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

Publié le 9 mars 2015
A+Augmenter la taille du texteA-Réduire la taille du texteImprimer le documentEnvoyer cette page par mail cet article Facebook Twitter Linked In
Colloque / Séminaire du 12 mars 2015 au 13 mars 2015

Jeudi 12 mars à 14h30, en salle C319, nous aurons le plaisir d'écouter Guilherme D. da Fonseca (LIRMM, Montpellier) :

 


Linear-Time Approximation Algorithms for Geometric Intersection Graphs




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.

A+Augmenter la taille du texteA-Réduire la taille du texteImprimer le documentEnvoyer cette page par mail cet article Facebook Twitter Linked In

mise à jour le 31 mars 2015

  • Tutelle CNRS
  • Tutelle Grenoble INP
  • Université Joseph Fourier
  • Tutelle UMR
Université Grenoble Alpes