Algorithmes d'approximation pour le chemin le plus court ₚ et l'arbre de Steiner ₚ-groupe

Nous présentons des algorithmes d'approximation polylogarithmiques pour les variantes des problèmes de chemin le plus court, d'arbre de Steiner groupe et de ATSP de groupe avec des coûts vectoriels. Dans ces problèmes, chaque arête e a un coût vectoriel non négatif cₑ R^₀. Pour une solution réalisable - un chemin, un sous-arbre ou une tournée (respectivement) - nous trouvons le coût total vectoriel de toutes les arêtes dans la solution et calculons ensuite la ₚ-norme du vecteur de coût obtenu (nous supposons que p 1 est un entier). Nos algorithmes pour les graphes en série-parallèle s'exécutent en temps polynomial et ceux pour les graphes arbitraires s'exécutent en temps quasi-polynomial. Pour obtenir nos résultats, nous introduisons et utilisons de nouvelles relaxations basées sur les flux de la somme des carrés. Nous obtenons également un certain nombre de résultats de difficulté.