## Packet Routing: Complexity and Algorithms

Research Area: Year: Algorithm Engineering for Real-time Scheduling and Routing 2010 In Collection Packet Routing, Complexity, NP-hardness, Approximation Algorithms Britta Peis; Martin Skutella; Andreas Wiese Springer Berlin 217-228 @incollection{packet-routing-WAOA, author = "Britta Peis and Martin Skutella and Andreas Wiese", abstract = "Routing of packets is one of the most fundamental tasks in a network. Limited bandwith requires that some packets cannot move to their destination directly but need to wait in intermediate nodes on their path or take detours. It is desirable to find schedules that ensure fast delivery of the packets, in particular for time critial applications. In this paper we investigate the packet routing problem theoretically. We prove that the problem cannot be approximated with a factor of $6/5-\epsilon$ for all $\epsilon>0$ unless $P=NP$. We show that restricting the graph topology to planar graphs or trees still does not allow a PTAS. For trees we give 2-approximation algorithms for the directed and the undirected case. Finally, we show that it is $NP$-hard to approximate the problem with an absolute error of $k$ for any $k\ge0$.", address = "Berlin", booktitle = "7th Workshop on Approximation and Online Algorithms (WAOA 2009)", institution = "Technische Universit{\"a}t Berlin", keywords = "Packet Routing, Complexity, NP-hardness, Approximation Algorithms", pages = "217--228", publisher = "Springer", series = "LNCS", title = "{P}acket {R}outing: {C}omplexity and {A}lgorithms", url = "http://dx.doi.org/10.1007/978-3-642-12450-1_20", volume = "5893", year = "2010", } Routing of packets is one of the most fundamental tasks in a network. Limited bandwith requires that some packets cannot move to their destination directly but need to wait in intermediate nodes on their path or take detours. It is desirable to find schedules that ensure fast delivery of the packets, in particular for time critial applications. In this paper we investigate the packet routing problem theoretically. We prove that the problem cannot be approximated with a factor of $6/5-\epsilon$ for all $\epsilon>0$ unless $P=NP$. We show that restricting the graph topology to planar graphs or trees still does not allow a PTAS. For trees we give 2-approximation algorithms for the directed and the undirected case. Finally, we show that it is $NP$-hard to approximate the problem with an absolute error of $k$ for any $k\ge0$. Online version [Bibtex]
[ Back ]