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.
Other formats:   BibTeX LaTeX RIS
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
Original language English
Type of outcome Proceedings paper
Field of Study 10201 Computer sciences, information science, bioinformatics
Country of publisher Switzerland
Confidentiality degree is not subject to a state or trade secret
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 0302-9743
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
Tags core_B, firank_B
Changed by Changed by: RNDr. Pavel Šmerk, Ph.D., učo 3880. Changed: 6/5/2016 06:18.
Abstract
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
PrintDisplayed: 25/9/2024 11:21