Séminaire (organisé par l’équipe de recherche RO)

Michal Pioro

Institute of Telecommunications, Warsaw University of Technology, Poland


A polynomial multicommodity flow problem with difficult path generationls


Vendredi 30 septembre à 12h en C221


Résumé :

In this talk, we consider a commonly know multicommodity network problem involving flow rerouting in case of failures, assuming 100% demand restoration and stub release. No compact linear programming (LP) formulation for the problem is know, and all know non-compact LP formulations of the problem require NP-hard path generation (pricing). Therefore, the problem itself is suspected to be NP-hard ? this, however, is not actually know. The main result of this work reveals a special case of the basic problem for which the resulting noncompact LP formulation still has an NP-hard pricing problem, the corresponding compact LP formulation is not know either, but the problem itselft is polynomial. The considered special case assumes only one failing link so that all the links but one are assumerd to be 100% reliable. The constructed case of a polynomial multicommodity flow problem with difficult path generation is of interest since no such problem is, to the best of our knowledge, widely know.

Seminars


Mardi 10 mai 2016

Séminaire à 14 h 30 en GI042 présenté par Christophe DENIS, Chargé de Formation et de Recherche au Centre de mathématiques et de leurs applications (CMLA), ENS Cachan. « Verificarlo : checking the floating point accuracy of scientific codes »


Lundi 14 mars 2016

Séminaire à 9 h en GI042, présenté par Ahcène Bounceur, Maître de conférence, HDR, à l’Université de Bretagne Occidentale (UBO). « CupCarbon : A New Platform for Simulating Smart Wireless Sensor Networks (SWSN) »


Mardi 9 février 2016

Séminaire à 14 h en GI042 présenté par Fabio D’Andreagiovanni, Chercheur senior et Directeur de projet au département d’optimisation de Zuse Institute Berlin (ZIB), Berlin (Allemagne). « Multiband Robust Optimization : theory and applications »


Jeudi 28 janvier 2016

Séminaire à 15 h 30 en GI042 présenté par Said Tabli, stagiaire au sein du laboratoire Heudiasyc. « Trust Management in Clustered Wireless Sensor Networks »


Pages 1 | 2 | 3 | 4 | 5 | 6 | 7




Actualités
Vidéothèque
Téléchargements
Annuaire



FR SHIC 3272

Collegium UTC/CNRS