Dans un réseau de communication mobile, les interlocuteurs doivent pouvoir s'identifier avec un certain degré de sécurité. D'où la nécessité d'associer à chaque interlocuteur un ensemble d'interlocuteurs fiables (identifiés avec garantie) par lesquels les liaisons transiteront.

Ceci pose des problèmes d'équilibrage qui s'expriment en termes de graphes. Nous en donnerons quelques formulations ainsi que des approches heuristiques. Enfin quelques cas particuliers seront examinés en exploitant la structure du graphe des communications. Des problèmes ouverts seront enfin mentionnés.

La gestion du revenu (développée, sous le nom de Yield Management, pour le transport aérien dans les années 1980 puis étendue, souvent sous le nom de Revenue Management, à de nombreuses autres industries) vise à optimiser le profit résultant de la vente d'un service ou d'un produit en coordonnant l'offre et la demande, en particulier par la segmentation du marché et la gestion en temps réel des prix et de la capacité. Un problème central en gestion du revenu est de décider, en temps réel, à quels clients et à quels prix vendre une capacité périssable, par exemple les places de passagers sur un certain vol.

Nous approchons ce problème du point de vue de l'analyse compétitive des algorithmes en-ligne (online), évaluant une politique (ou algorithme) par rapport à l'optimum hors-ligne (offline), lequel alloue cette capacité après avoir observé toute la demande. Cette approche permet de définir des politiques avec garantie de performance, et qui sont robustes lorsque la demande est difficile à prévoir.
Travaux en collaboration avec Michael O. Ball (University of Maryland).

Les logiciels de programmation en nombres entiers ont fait d'énormes progrès au cours des dix dernières années. Un des facteurs qui ont contribué à cette amélioration est l'introduction de coupes en conjonction avec les algorithmes de séparation habituels. En particulier, de nos jours, les coupes de Gomory jouent un role important dans les meilleurs logiciels. Toute amélioration de ces coupes peut donc se répercuter directement dans une amélioration des logiciels de programmation en nombres entiers, qui sont devenus d'après Bixby les plus gros consommateurs de programmes linéaires. Nous discuterons comment améliorer les coupes de Gomory. Nous aborderons également la question pratique d'estimer au bout de quelques secondes le temps de calcul nécessaire pour résoudre un programme en nombres entiers.

Cette présentation est basée sur des travaux réalisés en collaboration avec Yanjun Li (Université de Purdue), Kent Andersen et Miroslav Karamanov (Université de Carnegie Mellon).