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 Partagez cet article Facebook Twitter Linked In Google+ Viadeo
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) :

vignette-seminaireOC.jpg

vignette-seminaireOC.jpg

 


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 Partagez cet article Facebook Twitter Linked In Google+ Viadeo

mise à jour le 31 mars 2015

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