Complexity and Approximation Results for the Min-Sum and Min-Max Disjoint Paths Problems

In: Computing and Informatics, vol. 32, no. 1

P. Zhang - W. Zhao - D. Zhu

Detaily:

Rok, strany: 2013, 23 - 45

Kľúčové slová:

Disjoint paths, min-sum, min-max, computational complexity, approximation algorithms

O článku:

Given a graph G=(V, E) and k source-sink pairs (s1, t1), …, (sk, tk) with each si, ti V, the Min-Sum Disjoint Paths problem asks to find k disjoint paths connecting all the source-sink pairs with minimized total length, while the Min-Max Disjoint Paths problem asks for k disjoint paths connecting all the source-sink pairs with minimized length of the longest path. We show that the weighted Min-Sum Disjoint Paths problem is FPNP-complete in general graphs, and the unweighted Min-Sum Disjoint Paths problem and the unweighted Min-Max Disjoint Paths problem cannot be approximated within (m1-) for any constant  > 0 even in planar graphs, assuming P  NP, where m is the number of edges in G. We give for the first time a simple bicriteria approximation algorithm for the unweighted Min-Max Edge-Disjoint Paths problem and the weighted Min-Sum Edge-Disjoint Paths problem, with guaranteed approximation ratio O(log k / log log k) and O(1), respectively.

Ako citovať:

ISO 690:

Zhang, P., Zhao, W., Zhu, D. 2013. Complexity and Approximation Results for the Min-Sum and Min-Max Disjoint Paths Problems. In Computing and Informatics, vol. 32, no.1, pp. 23-45. 1335-9150.

APA:

Zhang, P., Zhao, W., Zhu, D. (2013). Complexity and Approximation Results for the Min-Sum and Min-Max Disjoint Paths Problems. Computing and Informatics, 32(1), 23-45. 1335-9150.