Actualités
  Période
semaine
ou mois
aucune période


  Thèmes:
Thèses
Colloques
Autres
Groupes
Tous les thèmes

   
  Liens:
Voir les thèses

Voir les colloques

Voir les autres événements

Voir la page des groupes

Accéder à l'intranet

Intitulé:   
Bin Packing avec Contrainte de Distance
du groupe GT Graphes et Applications

Date 2010-05-07  14:00-15:00
TitreBin Packing avec Contrainte de Distance 
RésuméLe Bin Packing est un problème NP-Complet classique: étant donné un ensemble d'éléments pondérés, on cherche à minimiser le nombre de groupes de poids borné (identique pour tous les groupes) nécessaires pour que chaque élément appartienne à un groupe. Nous ajoutons une contrainte supplémentaire à ce problème en considérant que les éléments à empaqueter sont placés dans un espace métrique. Deux éléments d'un même groupe ne doivent alors pas être à plus d'une certaine distance dmax préalablement fixée. Nous avons recours à de l'augmentation de ressources pour étudier ce problème: nous autorisons nos algorithmes à construire des groupes de diamètre b*dmax, et comparant le nombre de groupes créés à une solution optimale contrainte à construire des groupes de diamètre dmax. Cette augmentation de ressources est nécessaire puisque nous prouvons que pour tout e>0, il n'existe pas d'algorithme d'approximation à facteur constant pour le bin packing avec distance contrainte utilisant une augmentation de ressource de (2-e). Nous prouvons également que quelque soit l'augmentation de ressource qu'on veut utiliser, il n'existe pas d'algorithme approchant à un facteur inférieur à 3/2 la solution optimale contrainte à dmax. Nous présenterons ensuite un algorithme utilisant une augmentation de ressource de 2, et produisant un facteur d'approximation de 7/3. Enfin nous présentons une équivalence entre le bin packing avec contrainte de distance et le problème du k-centre avec capacité, un autre problème NP-Complet classique. Nos résultats sur le bin packing avec contrainte de distance implique les premiers résultats connus sur la variante non uniforme du k-centre avec capacité. 
Lieusalle 178 
OrateurHubert Larchevêque 



Aucun document lié à cet événement.

Retour
Retour à l'index