Premium
Approximability of unsplittable shortest path routing problems
Author(s) -
Bley Andreas
Publication year - 2009
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20303
Subject(s) - mathematics , combinatorics , shortest path problem , routing (electronic design automation) , digraph , undirected graph , directed graph , discrete mathematics , path (computing) , graph , computer science , computer network , programming language
In this article, we discuss the relation of unsplittable shortest path routing (USPR) to other routing schemes and study the approximability of three USPR network planning problems. Given a digraph D = ( V , A ) and a set K of directed commodities, an USPR is a set of flow paths P * ( s , t ) , ( s , t ) ∈ K , such that there exists a metric λ = (λ a ) ∈ Z + Awith respect to which each P * ( s , t )is the unique shortest ( s , t )‐path. In the Min‐Con‐USPR problem, we seek an USPR that minimizes the maximum congestion over all arcs. We show that this problem is NP‐hard to approximate within a factor of O (| V | 1−ϵ ), but polynomially approximable within min(| A |,| K |) in general and within O (1) if the underlying graph is an undirected cycle or a bidirected ring. We also construct examples where the minimum congestion that can be obtained by USPR is a factor of Ω(| V | 2 ) larger than that achievable by unsplittable flow routing or by shortest multipath routing, and a factor of Ω(| V |) larger than that achievable by unsplittable source‐invariant routing. In the C AP ‐USPR problem, we seek a minimum cost installation of integer arc capacities that admit an USPR of the given commodities. We prove that this problem is NP‐hard to approximate within 2 − ϵ even in the undirected case, and we devise approximation algorithms for various special cases. The fixed charge network design problem FC‐USPR, where the task is to find a minimum cost subgraph of D whose fixed arc capacities admit an USPR of the commodities, is shown to be NPO‐complete. All three problems are of great practical interest in the planning of telecommunication networks that are based on shortest path routing protocols. Our results indicate that they are harder than the corresponding unsplittable flow or shortest multi‐path routing problems. © 2009 Wiley Periodicals, Inc. NETWORKS, 2009