Journées Franciliennes de Recherche Opérationnelle
ROADEF




Retour

Programme (JFRO)

Approximation polynômiale

Université Paris Dauphine

Amphi 1
Place du Maréchal de Lattre de Tassigny
75016 Paris - Métro Porte Dapuhine

9h45 - 10h

Accueil des participants

10h - 12h

 

Tutorial : L' APPROXIMATION POLYNOMIALE ET SES ENJEUX

Vangélis PASCHOS - LAMSADE - Université Paris Dauphine

 

Transparents de l'exposé (au format PDF) - Transparents de l'exposé (au format postscript)

 

Nous présenterons les buts et les principes de la théorie de l'approximation polynomiale ainsi que ses principaux outils tels que les mesures de qualité (rapports classique et différentiel) et les réductions préservant l'approximation. Nous illustrerons tout ceci par des résultats d'approximation pour quelques problèmes connus d'optimisation combinatoire. Nous finirons en présentant quelques nouveaux aspects de la problématique de l'approximation polynomiale.

 12h - 13h45

DÉJEUNER

13h45-14h30

 

AUGMENTATION DE GRAPHES SOUS CONTRAINTES DE BICONNEXITE ET DE DIAMETRE

Yann VAXES - LIF - Faculté des Sciences de Luminy

 

Transparents de l'exposé (au format PDF)

 

On présente quelques résultats antérieurs et questions ouvertes autour du problème suivant. Etant donné un graphe G=(V, E) et un entier positif D, trouver un ensemble d'arêtes de cardinalité minimum tel que le graphe augmenté G'=(V, E U E') soit biconnexe et de diamètre au plus D.

14h30-15h15

 

OPT versus LOAD in DYNAMIC STORAGE ALLOCATION

Claire KENYON - LIX - Ecole Polytechnique

 

Adam L. Buchsbaum and Howard Karloff and Claire Kenyon and Nick Reingold and Mikkel Thorup

Dynamic Storage Allocation is the problem of packing given axis-aligned rectangles into a horizontal strip of minimum height by sliding the rectangles vertically but not horizontally. Where L is the maximum sum of heights of rectangles that intersect any vertical line and OPT is the minimum height of the enclosing strip, it is obvious that OPT>L; previous work showed that OPT<3L. We continue the study of the relationship between OPT and L, proving that OPT=L+o(L) when the maximum job height is o(L).

En route, we construct several new polynomial-time approximation algorithms for in Dynamic Storage Allocation.

 15h15 - 15h45

PAUSE

15h45-16h30

OPTIMSATION MULTICRITERE ET APPROXIMATION POLYNOMIALE

Euripides BAMPIS - LAMI - Université d'Evry

 

Transparents de l'exposé (au format PDF)