Efficient delay routing

AbstractIn this paper the computational complexity of finding packet routing schemes provably efficient with respect to the end-to-end delay is studied. The attention is focused on polynomial-time algorithms able to optimize the end-to-end delay when the number of packets in the network increases, and the number of packets that can be accepted in the network in order to keep the end-to-end delay within a constant value. In particular, the hardness of approximating in polynomial time both the minimum end-to-end delay and the maximum number of accepted packets within any sublinear error in the number of packets is proved