Skip to Main content Skip to Navigation

Approximation de l'arborescence de Steiner

Abstract : The directed Steiner tree problem (DST) asks, considering a directed weighted graph, a node r called root and a set of nodes X called terminals, for a minimum cost directed tree rooted in r spanning X. DST is an NP-complete problem. We are interested in the search for polynomial approximations for DST. Unless P = NP, DST can not be approximated neither within a constant ratio nor a logarithmic ratio with respected to k, where k is the number of terminals. The smallest known approximation ratio is O(kԑ) where ԑ is a positive real.In the first part, we provide three new approximation algorithms : a practical greedy algorithm merging two of the main approximation techniques for DST, an algorithm for the case where the graph is layered and where the distance between the terminals and the root is high, and an exponential approximation algorithm combining an approximation algorithm and an exact algorithm, parameterized with the number of terminals the exact algorithm must cover.In the last part we study DST with two branching constraints. With this technique, we are able to reduce the number of feasible solutions, and possibly facilitate the search for an optimal solution of the constraint problem. We study how it is possible to build such a solution in polynomial time and if this solution is a good approximation of an optimal solution of the non-constraint problem
Document type :
Complete list of metadata

Cited literature [72 references]  Display  Hide  Download
Contributor : Abes Star :  Contact
Submitted on : Wednesday, March 11, 2015 - 9:55:06 AM
Last modification on : Monday, December 14, 2020 - 12:38:07 PM
Long-term archiving on: : Friday, June 12, 2015 - 10:21:22 AM


Version validated by the jury (STAR)


  • HAL Id : tel-01130029, version 1



Dimitri Watel. Approximation de l'arborescence de Steiner. Autre [cs.OH]. Université de Versailles-Saint Quentin en Yvelines, 2014. Français. ⟨NNT : 2014VERS0025⟩. ⟨tel-01130029⟩



Record views


Files downloads