FENNER, T., O. LACHISCH a Alexandru POPA. Min-sum 2-paths problems. In 11th International Workshop on Approximation and Online Algorithms, WAOA 2013, LNCS 8447. Sophia Antipolis; France: Springer. s. 1-11. ISBN 978-3-319-08000-0. doi:10.1007/978-3-319-08001-7_1. 2014.
Další formáty:   BibTeX LaTeX RIS
Základní údaje
Originální název Min-sum 2-paths problems
Autoři FENNER, T. (826 Velká Británie a Severní Irsko), O. LACHISCH (826 Velká Británie a Severní Irsko) a Alexandru POPA (642 Rumunsko, domácí).
Vydání Sophia Antipolis; France, 11th International Workshop on Approximation and Online Algorithms, WAOA 2013, LNCS 8447, od s. 1-11, 11 s. 2014.
Nakladatel Springer
Další údaje
Originální jazyk angličtina
Typ výsledku Stať ve sborníku
Obor 10201 Computer sciences, information science, bioinformatics
Stát vydavatele Švýcarsko
Utajení není předmětem státního či obchodního tajemství
Forma vydání tištěná verze "print"
Impakt faktor Impact factor: 0.402 v roce 2005
Kód RIV RIV/00216224:14330/14:00087424
Organizační jednotka Fakulta informatiky
ISBN 978-3-319-08000-0
ISSN 0302-9743
Doi http://dx.doi.org/10.1007/978-3-319-08001-7_1
Klíčová slova anglicky Additive polynomials; Edge-disjoint paths; K-paths; Min-sum; NP-hardness; Ordered pairs; Running time; Undirected graph
Štítky firank_B
Změnil Změnil: RNDr. Pavel Šmerk, Ph.D., učo 3880. Změněno: 6. 5. 2016 06:18.
Anotace
An orientation of an undirected graph G is a directed graph obtained by replacing each edge {u,v} of G by exactly one of the arcs (u,v) or (v,u). In the min-sum k-paths orientation problem, the input is an undirected graph G and ordered pairs (s i ,t i ), where i in {1,2,...,k}. The goal is to find an orientation of G that minimizes the sum over every i in {1,2,...,k} of the distance from s i to t i . In the min-sum k edge-disjoint paths problem the input is the same, however the goal is to find for every i in {1,2,...,k} a path between s i and t i so that these paths are edge-disjoint and the sum of their lengths is minimum. Note that, for every fixed k >= 2, the question of NP-hardness for the min-sum k-paths orientation problem and the min-sum k edge-disjoint paths problem have been open for more than two decades. We study the complexity of these problems when k = 2. We exhibit a PTAS for the min-sum 2-paths orientation problem. A by-product of this PTAS is a reduction from the min-sum 2-paths orientation problem to the min-sum 2 edge-disjoint paths problem. The implications of this reduction are: (i) an NP-hardness proof for the min-sum 2-paths orientation problem yields an NP-hardness proof for the min-sum 2 edge-disjoint paths problem, and (ii) any approximation algorithm for the min-sum 2 edge-disjoint paths problem can be used to construct an approximation algorithm for the min-sum 2-paths orientation problem with the same approximation guarantee and only an additive polynomial increase in the running time
VytisknoutZobrazeno: 28. 3. 2024 16:00