Approximating Bicriteria Network-Design Problems

该项目涉及为计算机网络中出现的基本问题设计近似算法，其中节点需要在某些约束下相互通信。在任何两个节点之间建立直接链接都有相应的成本。对于不同的节点对，这个代价是不同的。有几个约束条件，例如，典型的需求是每个节点都能够通过一系列链接到达其他节点。其他一些约束的例子是在节点故障的情况下使网络健壮，节点之间的通信路径平均较短，以及为链路购买足够的带宽以支持预期的流量（更多的带宽成本更高，但允许更多的数据量在每单位时间内在链路上传递）。给定链路成本和网络约束，目标是设计一个满足约束的网络，这样网络成本就不会太大。所提出的问题在超大规模集成电路、制造、大批量采购等方面都有应用。对这些问题的理论见解可能会导致对问题的更好理解。

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.