PhD Defense: Allocation Algorithms for Networks with Scarce Resources

Many fundamental algorithmic techniques have roots in applications to computer networks. We consider several problems that prop up in wireless ad hoc networks, sensor networks, P2P networks, and cluster networks. Here, the common challenge is to deal with certain bottleneck resources that are crucial for the performance of underlying system.
Broadly, we deal with the following issues.
Data: In resource replication problems, the primary goal is to replicate data objects on server nodes with limited storage capacities, so that the latency of client nodes needing these objects is minimized. Previous work in this area is heuristic and without guarantees. We develop tight (or nearly) approximation algorithms for several problems including basic resource replication - where clients need all objects and server can store at most one object, subset resource replication - where clients require different subsets of objects and servers have limited non-uniform capacity, and related variants.
Computational resources: In cluster networks, to facilitate packing of jobs needing disparate amounts of computational resources, an important auxiliary problem to solve is that of container selection. The idea is to select a limited number of "containers" that represent a given pool of jobs while minimizing "wastage" of resources. Subsequently, instead of packing jobs, containers representing them can be packed. We show that the continuous variant of this problem, where there are no additional restrictions on chosen containers, is NP-hard and admits a polynomial time approximation scheme. The discrete variant, where containers must be chosen from a given set, is shown to be NP-hard to even approximate and therefore we focus on obtaining bi-approximation algorithms.
Energy resources: Wireless ad hoc networks contain nodes with limited battery life and it is crucial to design energy efficient algorithms. We obtain tight approximation (up to constant factors) guarantees for partial and budgeted versions of the connected dominating set problem which is regarded as a good model for a virtual backbone of a wireless ad hoc network. Further, we will discuss approximation algorithms for some problems involving target monitoring in sensor networks and message propagation in radio networks.
We will end with a discussion on future work.
Examining Committee:
Committee Chair: - Dr. Samir Khuller
Dean's Representative - Dr. Mark A. Shayman
Committee Members: - Dr. Mohammad Taghi Hajiaghayi
- Dr. Peter Keleher
- Dr. Aravind Srinivasan