Approximation Solutions for Time-Varying Shortest Path Problem

Document Type : Original paper


1 University of Qom

2 Unuversity of Qom


Abstract. Time-varying network optimization problems have tradition-
ally been solved by specialized algorithms. These algorithms have NP-
complement time complexity. This paper considers the time-varying short-
est path problem, in which can be optimally solved in O(T(m + n)) time,
where T is a given integer. For this problem with arbitrary waiting times,
we propose an approximation algorithm, which can solve the problem with
O(T(m+n)/ k ) time complexity such that evaluates only a subset of the values
for t = {0, 1, . . . , T}.


Main Subjects