%0 Journal Article
%T Approximation Solutions for Time-Varying Shortest Path Problem
%J Communications in Combinatorics and Optimization
%I Azarbaijan Shahid Madani University
%Z 2538-2128
%A Shirdel, Gholam Hassan
%A Rezapour, Hassan
%D 2017
%\ 09/01/2017
%V 2
%N 2
%P 139-147
%! Approximation Solutions for Time-Varying Shortest Path Problem
%K Time-Varying Optimization
%K Approximation solutions
%K Shortest Path Problem
%R 10.22049/cco.2017.25850.1047
%X Time-varying network optimization problem, which is NP-complete in the ordinary sense, are traditionally solved by specialized algorithms. This paper considers the time-varying shortest path problem, which can be optimally solved in $Obig(T(m+n)big)$ time, where $T$ is a given integer. For this problem with arbitrary waiting times, we propose an approximate algorithm, which can find an acceptable solution of the problem with $Obig(frac{T(m+n)}{k}big)$ time complexity such that it evaluates only a subset of the values for $t in {0, 1,ldots,T}$.
%U http://comb-opt.azaruniv.ac.ir/article_13645_0d39e0bfe8ae0a66991a25e4ac1ac564.pdf