Approximation Algorithms for Networks

Illinois Institute Of Technology, Chicago IL

Investigators

Abstract

This project focuses on NP-hard optimization problems arising from the rapid development of Computer Networks. This research proposes to investigate the development of efficient combinatorial algorithms for wired and wireless networks. The project also involves improving the existing algorithms for fundamental graph optimization problems that have direct applications in networking. The PI proposes to concentrate on fast generation of approximate solutions. In addition, the algorithms for wireless networks must use only local information. Specifically, the PI intends to accomplish the following research items in this project: .. devise efficient approximation algorithms to increase bandwidth utilization in quality-of-service multicasting. .. devise efficient distributed algorithms for maintaining connectivity in ad hoc wireless networks and sensor networks, while minimizing the energy consumption and extending the network's lifetime. The PI will analyze the communication complexity of the algorithms and their behavior with imprecise input data and node failure. The research will start by concentrating on static networks, while always considering extensions to mobile networks. Once the problems arising from static ad-hoc wireless networks are better understood, the PI will concentrate on mobility. .. devise efficient approximation algorithms for several graph connectivity problems. .. identify and solve new optimization problems arising in the next generation of computer networks. The new methods will be grounded on provably good algorithms with guaranteed worst-case performance, and extensive empirical studies that thoroughly test the algorithms' efficiency in simulations on available industrial data. The developed algorithms and their implementations will be widely distributed to practitioners in order to enable a more complete understanding of the optimization problems in these application areas. The intelectual merit of this proposal consists of advances in the techniques of design and analysis of algorithms and the understanding of the underlying combinatorial structure of several graph optimization problems. The main educational goal of this project is to improve the preparation of graduate and undergraduate CS majors at Illinois Institute of Technology (IIT) in theoretical computer science. The grant would be used to support a research group of graduate and undergraduate students. The project's impact will be increased by supporting seminars and workshops which benefit a diversity of students and researchers. The PI's service agenda is centered on recruitment of talented students for theoretical research, as part of the broader impacts of the proposed research.