Min-sum 2-paths problems

D 2014

Min-sum 2-paths problems

FENNER, T., O. LACHISCH and Alexandru POPA

Basic information

Original name

Min-sum 2-paths problems

Authors

FENNER, T. (826 United Kingdom of Great Britain and Northern Ireland), O. LACHISCH (826 United Kingdom of Great Britain and Northern Ireland) and Alexandru POPA (642 Romania, belonging to the institution)

Edition

Sophia Antipolis; France, 11th International Workshop on Approximation and Online Algorithms, WAOA 2013, LNCS 8447, p. 1-11, 11 pp. 2014

Publisher

Springer

Other information

Language

English

Type of outcome

Stať ve sborníku

Field of Study

10201 Computer sciences, information science, bioinformatics

Country of publisher

Switzerland

Confidentiality degree

není předmětem státního či obchodního tajemství

Publication form

printed version "print"

Impact factor

Impact factor: 0.402 in 2005

RIV identification code

RIV/00216224:14330/14:00087424

Organization unit

Faculty of Informatics

ISBN

978-3-319-08000-0

ISSN

DOI

http://dx.doi.org/10.1007/978-3-319-08001-7_1

Keywords in English

Additive polynomials; Edge-disjoint paths; K-paths; Min-sum; NP-hardness; Ordered pairs; Running time; Undirected graph

Abstract

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 and 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, p. 1-11. ISBN 978-3-319-08000-0. Available from: 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 and 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, p.~1-11. ISBN~978-3-319-08000-0. Available from: https://dx.doi.org/10.1007/978-3-319-08001-7\_{}1.

Detailed Information on Publication Record