APPROXIMATING BICRITERIA NETWORK-DESIGN PROBLEMS

Project Details

Description

This project involves designing approximation algorithms forfundamental problems arising in computer networks in which nodes needto communicate with each other under some constraints.Building a direct link between any two nodes has a cost associatedwith it. This cost is different for different pairs of nodes. Thereare several constraints, for example, a typical requirement would bethat every node would be able to reach every other node by a sequenceof links. Examples of some other constraints are making the networkrobust in case of node failures, communication paths between nodesbeing short on average, and buying enough bandwidth for links tosupport the expected traffic (more bandwidth costs more but allowslarger quantity of data to be delivered on the link per time unit).Given the link costs, and the network constraints, the goal is todesign a network satisfying the constraints, such that the networkcost is not too large.The proposed problems have applications in VLSI, manufacturing, buyinglarge set of items at bulk and more. Theoretical insight into theseproblems is likely to lead to better understanding of the problems.
StatusFinished
Effective start/end date2/15/081/31/09

Funding

  • National Science Foundation (National Science Foundation (NSF))

Fingerprint

Explore the research topics touched on by this project. These labels are generated based on the underlying awards/grants. Together they form a unique fingerprint.