pr\u00e9sentent<\/p>\n\n\n\n
Autoris\u00e9 \u00e0 pr\u00e9senter ses travaux en vue de l\u2019obtention du Doctorat de l’Institut Polytechnique de Paris, pr\u00e9par\u00e9 \u00e0 T\u00e9l\u00e9com SudParis en :<\/p>\n\n\n\n
le MERCREDI 9 NOVEMBRE 2022 \u00e0 10h00<\/p>\n\n\n\n
Salle 4A101
19 PLACE MARGUERITE PEREY, 91120 PALAISEAU<\/p>\n\n\n\n
Membres du jury :<\/strong><\/p>\n\n\n\n M. Walid BEN-AMEUR<\/strong>, Professeur, T\u00e9l\u00e9com SudParis, FRANCE – Directeur de th\u00e8se \u00c9tant donn\u00e9e la nature dynamique du trafic, nous \u00e9tudions la variante du probl\u00e8me de dimensionnement robuste de r\u00e9seaux qui consiste \u00e0 d\u00e9terminer la capacit\u00e9 \u00e0 r\u00e9server sur chaque lien d’un r\u00e9seau de telle sorte que chaque demande appartenant \u00e0 un polytope donn\u00e9 puisse \u00eatre rout\u00e9e. L’objectif est soit de minimiser la congestion soit un co\u00fbt lin\u00e9aire. Nous \u00e9tudions tout d’abord l’approximabilit\u00e9 de la variante avec un routage fractionnaire et dynamique dans des graphes non dirig\u00e9s. Nous prouvons tout d’abord que, sauf si $P=NP$ le probl\u00e8me de minimisation de la congestion ne peut \u00eatre approch\u00e9 en dessous d’aucun facteur constant r\u00e9pondant ainsi \u00e0 une question ouverte de Chekuri (2007). Ensuite, en utilisant la conjecture ETH, nous prouverons une borne inf\u00e9rieure de $Omega(log n \/ log log n )$ sur l’approximabilit\u00e9 de ce probl\u00e8me. Nous portons ensuite notre attention sur la variante avec un graphe dirig\u00e9. Nous montrons qu’une solution avec un routage statique optimal donne une $O(sqrt{k}) = O(n)$-approximation du routage dynamique optimal, o\u00f9 $k$ est le nombre de commodit\u00e9s et $n$ le nombre de noeuds. Nous montrons ensuite qu’une g\u00e9n\u00e9ralisation naturelle du probl\u00e8me ne peut \u00eatre approch\u00e9 en dessous d’un facteur de $k^{frac{ c }{ log log k }}$ pour une certaine constante $c$ (resp. $2^{log^{1- epsilon} k }$ pour tout $epsilon > 0$) sauf si $NP subseteq SUBEXP$ (resp. $NP subseteq QP$). Nous \u00e9tudions \u00e9galement plusieurs reformulations du probl\u00e8me de dimensionnement robuste de r\u00e9seaux permettant d’am\u00e9liorer la m\u00e9thode de routage affine. Nous montrons tout d’abord que la formulation par noeud-arc peut \u00eatre moins restrictive que la formulation par arc-chemin. Nous fournissons \u00e9galement une formulation naturelle \u00e9quivalente a la formulation par noeud-arc. Nous \u00e9tudions ensuite plusieurs formulations bas\u00e9es sur des relaxations des contraintes de conservation de flot. Ensuite, nous \u00e9tudions des formulations bas\u00e9es sur des agr\u00e9gations de commodit\u00e9 par source ou par destination. Enfin nous proposons une strat\u00e9gie interm\u00e9diaire entre l’approche statique et l’approche dynamique pour s’approcher encore plus du dynamique tout en contr\u00f4lant la complexit\u00e9. Il s’agit d’une approche qu’on pourrait qualifier de multi-statique. L’id\u00e9e est de choisir un ensemble de faces du polytope repr\u00e9sentant l’ensemble d’incertitude de telle mani\u00e8re que l’union des ces faces contienne tous les points extr\u00eames non-domin\u00e9s de cet ensemble. Un routage statique est consid\u00e9r\u00e9 pour chacune de ces faces. Given the dynamic nature of traffic, we investigate the robust network design problem where we have to determine the capacity to reserve on each link so that each demand vector belonging to a polyhedral set can be routed. The objective is either to minimize congestion or a linear cost. When routing is assumed to be fractional and dynamic (i.e., dependent on the current traffic vector), we first prove that the robust network design problem with minimum congestion cannot be approximated within any constant factor, settling an open question by Chekuri (2007). Then, using the ETH conjecture, we get a $Omega(frac{log n}{log log n})$ lower bound for the approximability of this problem. We next focus on the variant in which the underlying graph is directed. We prove that an $O(sqrt{k}) = O(n)$-approximation can be obtained by solving the problem under static routing, where $k$ is the number of commodities and $n$ is the number of nodes. We show that a natural generalization of the problem cannot be approximated within a ratio of $k^{frac{ c }{ log log k }} $ for some constant $c$ (resp. $2^{log^{1- epsilon} k }$ for any $epsilon >0$) unless $NP subseteq SUBEXP$ (resp. $NP subseteq QP$). Affine routing can be used to obtain better solutions also with polynomial-time algorithms. It consists in restricting the routing to depend on the demands in an affine way. We first show that a node-arc formulation is less conservative than an arc-path formulation. We also provide a natural cycle-based formulation that is shown to be equivalent to the node-arc formulation. To further reduce the solution’s cost, several new formulations are proposed. They are based on the relaxation of flow conservation constraints. The obtained formulations have been further improved through aggregation. As might be expected, aggregation allows us to reduce the size of formulations. A more striking result is that aggregation reduces the solution’s cost. We finally propose an intermediate strategy between static and dynamic routing that can be seen as a new variant of multi-static routing. We consider some faces of the uncertainty set whose union contains all non-dominated extreme points of the polytope. Then a static routing is considered for each of these faces.<\/p>\n","protected":false},"excerpt":{"rendered":" L’Ecole doctorale : Ecole Doctorale de l’Institut Polytechnique de Pariset le Laboratoire de recherche SAMOVAR – Services r\u00e9partis, Architectures, MOd\u00e9lisation, Validation, Administration des R\u00e9seaux pr\u00e9sentent l\u2019AVIS DE SOUTENANCE de Monsieur Yacine AL NAJJAR Autoris\u00e9 \u00e0 pr\u00e9senter ses travaux en vue de l\u2019obtention du Doctorat de l’Institut Polytechnique de Paris, pr\u00e9par\u00e9 \u00e0 T\u00e9l\u00e9com SudParis en : […]<\/p>\n","protected":false},"author":4,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"ocean_post_layout":"","ocean_both_sidebars_style":"","ocean_both_sidebars_content_width":0,"ocean_both_sidebars_sidebars_width":0,"ocean_sidebar":"0","ocean_second_sidebar":"0","ocean_disable_margins":"enable","ocean_add_body_class":"","ocean_shortcode_before_top_bar":"","ocean_shortcode_after_top_bar":"","ocean_shortcode_before_header":"","ocean_shortcode_after_header":"","ocean_has_shortcode":"","ocean_shortcode_after_title":"","ocean_shortcode_before_footer_widgets":"","ocean_shortcode_after_footer_widgets":"","ocean_shortcode_before_footer_bottom":"","ocean_shortcode_after_footer_bottom":"","ocean_display_top_bar":"default","ocean_display_header":"default","ocean_header_style":"","ocean_center_header_left_menu":"0","ocean_custom_header_template":"0","ocean_custom_logo":0,"ocean_custom_retina_logo":0,"ocean_custom_logo_max_width":0,"ocean_custom_logo_tablet_max_width":0,"ocean_custom_logo_mobile_max_width":0,"ocean_custom_logo_max_height":0,"ocean_custom_logo_tablet_max_height":0,"ocean_custom_logo_mobile_max_height":0,"ocean_header_custom_menu":"0","ocean_menu_typo_font_family":"0","ocean_menu_typo_font_subset":"","ocean_menu_typo_font_size":0,"ocean_menu_typo_font_size_tablet":0,"ocean_menu_typo_font_size_mobile":0,"ocean_menu_typo_font_size_unit":"px","ocean_menu_typo_font_weight":"","ocean_menu_typo_font_weight_tablet":"","ocean_menu_typo_font_weight_mobile":"","ocean_menu_typo_transform":"","ocean_menu_typo_transform_tablet":"","ocean_menu_typo_transform_mobile":"","ocean_menu_typo_line_height":0,"ocean_menu_typo_line_height_tablet":0,"ocean_menu_typo_line_height_mobile":0,"ocean_menu_typo_line_height_unit":"","ocean_menu_typo_spacing":0,"ocean_menu_typo_spacing_tablet":0,"ocean_menu_typo_spacing_mobile":0,"ocean_menu_typo_spacing_unit":"","ocean_menu_link_color":"","ocean_menu_link_color_hover":"","ocean_menu_link_color_active":"","ocean_menu_link_background":"","ocean_menu_link_hover_background":"","ocean_menu_link_active_background":"","ocean_menu_social_links_bg":"","ocean_menu_social_hover_links_bg":"","ocean_menu_social_links_color":"","ocean_menu_social_hover_links_color":"","ocean_disable_title":"default","ocean_disable_heading":"default","ocean_post_title":"","ocean_post_subheading":"","ocean_post_title_style":"","ocean_post_title_background_color":"","ocean_post_title_background":0,"ocean_post_title_bg_image_position":"","ocean_post_title_bg_image_attachment":"","ocean_post_title_bg_image_repeat":"","ocean_post_title_bg_image_size":"","ocean_post_title_height":0,"ocean_post_title_bg_overlay":0.5,"ocean_post_title_bg_overlay_color":"","ocean_disable_breadcrumbs":"default","ocean_breadcrumbs_color":"","ocean_breadcrumbs_separator_color":"","ocean_breadcrumbs_links_color":"","ocean_breadcrumbs_links_hover_color":"","ocean_display_footer_widgets":"default","ocean_display_footer_bottom":"default","ocean_custom_footer_template":"0","ocean_post_oembed":"","ocean_post_self_hosted_media":"","ocean_post_video_embed":"","ocean_link_format":"","ocean_link_format_target":"self","ocean_quote_format":"","ocean_quote_format_link":"post","ocean_gallery_link_images":"off","ocean_gallery_id":[],"footnotes":""},"categories":[286,615,613],"tags":[],"class_list":["post-4784","post","type-post","status-publish","format-standard","hentry","category-fractualites-ennews-fr","category-seminaire-sop","category-sop","entry"],"_links":{"self":[{"href":"https:\/\/samovar.telecom-sudparis.eu\/index.php\/wp-json\/wp\/v2\/posts\/4784","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/samovar.telecom-sudparis.eu\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/samovar.telecom-sudparis.eu\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/samovar.telecom-sudparis.eu\/index.php\/wp-json\/wp\/v2\/users\/4"}],"replies":[{"embeddable":true,"href":"https:\/\/samovar.telecom-sudparis.eu\/index.php\/wp-json\/wp\/v2\/comments?post=4784"}],"version-history":[{"count":2,"href":"https:\/\/samovar.telecom-sudparis.eu\/index.php\/wp-json\/wp\/v2\/posts\/4784\/revisions"}],"predecessor-version":[{"id":4786,"href":"https:\/\/samovar.telecom-sudparis.eu\/index.php\/wp-json\/wp\/v2\/posts\/4784\/revisions\/4786"}],"wp:attachment":[{"href":"https:\/\/samovar.telecom-sudparis.eu\/index.php\/wp-json\/wp\/v2\/media?parent=4784"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/samovar.telecom-sudparis.eu\/index.php\/wp-json\/wp\/v2\/categories?post=4784"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/samovar.telecom-sudparis.eu\/index.php\/wp-json\/wp\/v2\/tags?post=4784"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
M. Arie KOSTER<\/strong>, Professeur, RWTH Aachen University en Allemagne – Rapporteur
Mme Joanna TOMASIK<\/strong>, Professeure, Centrale Sup\u00e9lec, FRANCE – Rapporteure
M. Adam OUOROU <\/strong>, Directeur de recherche, Orange Labs, FRANCE – Examinateur
M. Michael POSS<\/strong>, Directeur de recherche, Chercheur CNRS au LIRMM, FRANCE – Examinateur
M. Olver NEIL<\/strong>, Associate Professor, London School of Economics and Political Science, ROYAUME-UNI – Examinateur
M. J\u00e9r\u00e9mie LEGUAY<\/strong>, Charg\u00e9 de recherche, Huawei Technologies France , FRANCE – Co-encadrant de th\u00e8qse
R\u00e9sum\u00e9 :<\/strong><\/p>\n\n\n\n
Abstract : \u00ab\u00a0Adaptive Robust Optimization for Network and Traffic Management\u00a0\u00bb<\/strong><\/p>\n\n\n\n