Algorithmique, Combinatoire et Recherche Opérationnelle
Laboratoire d'Informatique Fondamentale de Marseille

Journée CALM au LIF


Journée Combinatoire et Algorithmes du Littoral Méditerranéen

le 28 Janvier 2008 au LIF (Marseille)

sur le thème

Combinatoire Géométrique des Familles d’Ensembles

Il s’agira de présenter des outils issus de la géométrie discrète qui se sont révélés utiles pour étudier les propriétés combinatoires de certaines familles d’ensembles. En particulier, les sujets suivants seront abordés : Théorème de Helly fractionnaire, Transversaux, Couverture, Epsilon-Réseaux, (p,q)-propriété de Hadwiger-Debrunner, VC-Dimension.

Les chapitres 8,9,10 du livre de Matousek "Lectures on Discrete Geometry" Springer 2002, constituent une bonne introduction à ce thème. Les papiers suivants serviront aussi de source pour les exposés de cette journée.

H. Bronnimann and M. T. Goodrich, Almost optimal set covers in finite VC-dimension, Discrete & Computational Geometry, 14 (1995), pp. 263—279.

V. Chepoi, B. Estellon, Y. Vaxés, On covering planar graphs with a fixed number of balls, Discrete & Computional Geometry, 37 (2007), 237-244.

J. Matousek, Bounded VC-Dimension Implies a Fractional Helly Theorem, Discrete & Computational Geometry, 31 (2004), pp. 251-255.

Contacts :

Equipes participantes :

Liste des participants : ici

Lieu : Parc Scientifique et Technologique de Luminy, Faculté des Sciences, Batiment B, Amphi 12.

Programme provisoire : ici

Informations pratiques : ici

Présentation des JCALM : ici.

Journées précédentes :

Dernière modification : 29 avril 2008