Approximating Bicriteria Network-Design Problems

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.