| Speaker: | Guoliang (Larry) Xue |
| Department of Computer Science and Engineering | |
| Arizona State University |
Title: Finding a Path Subject to Many Additive QoS Constraints
Abstract:
A fundamental problem in quality-of-service (QoS) routing is to find a path between a specified source-destination node pair that satisfies K additive QoS constraints, where K>=2 is a constant integer. This problem is known to be NP-complete. For the case where K=2, several versions of FPTAS are known. We concentrate on the general problem where K is any constant greater than or equal to 2.
We first present a very simple K-approximation algorithm that can be used in hop-by-hop routing, with a time complexity essentially the same as that for computing a shortest path. We then make use of this K-approximation algorithm to design a fully polynomial time approximation scheme (FPTAS). When reduced to the case of K=2, our FPTAS has a better running time than the current best FPTAS.
Bio of Speaker:
Guoliang (Larry) Xue is a Professor of Computer Science and Engineering at Arizona State University. He received the PhD degree in Computer Science from the University of Minnesota in 1991. He has held previous positions as Assistant Professor/Associate Professor of Computer Science at the University of Vermont. His research interests are in networking and bioinformatics. He currently serves on the editorial boards of IEEE Network, Computer Networks, and International Journal of Sensor Networks.
