approximation solutions for time-varying shortest path problem

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 o t((m+n) ) 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 o (t (m+n)/k)
time complexity such that it evaluates only a subset of the values for t ∈ {0, 1, . . . , t }