This project involves designing approximation algorithms for fundamental problems arising in computer networks in which nodes need to communicate with each other under some constraints.
Building a direct link between any two nodes has a cost associated with it. This cost is different for different pairs of nodes. There are several constraints, for example, a typical requirement would be that every node would be able to reach every other node by a sequence of links. Examples of some other constraints are making the network robust in case of node failures, communication paths between nodes being short on average, and buying enough bandwidth for links to support the expected traffic (more bandwidth costs more but allows larger quantity of data to be delivered on the link per time unit).
Given the link costs, and the network constraints, the goal is to design a network satisfying the constraints, such that the network cost is not too large.
The proposed problems have applications in VLSI, manufacturing, buying large set of items at bulk and more. Theoretical insight into these problems is likely to lead to better understanding of the problems.
