Min-sum 2-paths problems

D 2014

Min-sum 2-paths problems

FENNER, T., O. LACHISCH a Alexandru POPA

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

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

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

core_B, firank_B

Změněno: 6. 5. 2016 06:18, RNDr. Pavel Šmerk, Ph.D.

Anotace

V originále

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

Citovat

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, 2014, s. 1-11. ISBN 978-3-319-08000-0. Dostupné z: https://dx.doi.org/10.1007/978-3-319-08001-7_1.

@inproceedings{1344384,
   author = {Fenner, T. and Lachisch, O. and Popa, Alexandru},
   address = {Sophia Antipolis; France},
   booktitle = {11th International Workshop on Approximation and Online Algorithms, WAOA 2013, LNCS 8447},
   doi = {http://dx.doi.org/10.1007/978-3-319-08001-7_1},
   keywords = {Additive polynomials; Edge-disjoint paths; K-paths; Min-sum; NP-hardness; Ordered pairs; Running time; Undirected graph},
   howpublished = {tištěná verze "print"},
   language = {eng},
   location = {Sophia Antipolis; France},
   isbn = {978-3-319-08000-0},
   pages = {1-11},
   publisher = {Springer},
   title = {Min-sum 2-paths problems},
   year = {2014}
}

TY  - JOUR
ID  - 1344384
AU  - Fenner, T. - Lachisch, O. - Popa, Alexandru
PY  - 2014
TI  - Min-sum 2-paths problems
PB  - Springer
CY  - Sophia Antipolis; France
SN  - 9783319080000
KW  - Additive polynomials
KW  - Edge-disjoint paths
KW  - K-paths
KW  - Min-sum
KW  - NP-hardness
KW  - Ordered pairs
KW  - Running time
KW  - Undirected graph
N2  - 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
ER  -

FENNER, T., O. LACHISCH a Alexandru POPA. Min-sum 2-paths problems. In \textit{11th International Workshop on Approximation and Online Algorithms, WAOA 2013, LNCS 8447}. Sophia Antipolis; France: Springer, 2014, s.~1-11. ISBN~978-3-319-08000-0. Dostupné z: https://dx.doi.org/10.1007/978-3-319-08001-7\_{}1.

Podrobný výpis o publikaci