|
|
 |
|
Mardi 4 Mars
| Heure: |
12:00 - 13:30 |
| Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
| Résumé: |
Problème de placement orthogonal |
| Description: |
Petru Valicov Etant donné un conteneur rectangulaire C, on s'intéresse à
décider si un ensemble d'items rectangulaires peut être placé sans
chevauchement et sans dépassement des bords de C. Une contrainte
supplémentaire est prise en compte -- l'interdiction de rotation des
items. Ce problème est NP-complet et est un sous-problème du problème de
sac-à-dos orthogonal où à chaque item on associe un profit et on cherche
le sous-ensemble d'items réalisable de profit total maximum. Fekete et
Schepers ont introduit une caractérisation élégante des solutions du
problème de placement en utilisant les graphes d'intervalles. Nous
présentons une nouvelle caractérisation en utilisant des MPQ-arbres --
des structures de données qui encodent efficacement les graphes
d'intervalles. Un des principaux avantages de cette caractérisation est
un nombre plus restreint des solutions symétriques traitées lors de
l'exécution de l'algorithme. Nous finiront par présenter une comparaison
des résultats avec ceux de la littérature sur les jeux de données
connus. Travail effectué en collaboration avec C. Joncour et A. Pêcher. |
|
|
