Écart d'intégralité polynomial du flux LP pour l'arbre de Steiner dirigé

Dans le problème de l'arbre de Steiner dirigé (DST), nous avons un graphe dirigé \ (G= (V, E) \) avec \ (n\) sommets et des coûts d'arête \ (cR ₀^E\), un sommet racine \ (r V\), et un ensemble \ (K V\r\\) de \ (k\) terminaux. L'objectif est de trouver un sous-graphe de coût minimum de \ (G\) qui contient un chemin de \ (r\) à chaque terminal \ (t K\). Le DST est un problème notoire depuis des décennies car il existe un grand écart entre le meilleur ratio d'approximation en temps polynomial connu de \ (O (k^) \) pour toute constante \ (0\), et le meilleur ratio d'approximation en temps quasi-polynomial de \ (O (^2k k) \). Dans le but de comprendre cet écart, nous étudions l'écart d'intégralité de la relaxation standard de programmation linéaire de flux pour le problème. Nous montrons que le programme linéaire (LP) a un écart d'intégralité de \ ( (n^0. 0418) \). Auparavant, l'écart d'intégralité du LP n'était connu que pour être \ ( (^2n n) \) Halperin et al., SODA’03 & SIAM J. Comput. et \ ( (k) \) Zosin-Khuller, SODA’02 dans certains cas avec \ (k=O (n n) \). Notre résultat donne la première borne inférieure connue sur l'écart d'intégralité de ce LP standard qui est polynomial en \ (n\), le nombre de sommets. Par conséquent, nous excluons la possibilité de développer un algorithme d'approximation poly-logarithmique pour le problème basé sur la relaxation LP de flux.