Approximating Bicriteria Network-Design Problems

近似双标准网络设计问题

• 批准号: 0728787
• 负责人: Guy Kortsarz
• 金额: $ 5.79万
• 依托单位: Rutgers University Camden
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2008
• 资助国家: 美国
• 起止时间: 2008-02-15 至 2009-01-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0728787&HistoricalAwards=false
• 关键词: 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.

该项目涉及在计算机网络中设计近似算法，即在计算机网络中出现的基础问题，其中节点需要在某些约束下相互通信。构建任何两个节点之间的直接链接都具有与之相关的成本。 对于不同的节点，此成本是不同的。 例如，例如，典型的需求将使每个节点都能通过链接序列到达其他所有节点。 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不太大。拟议的问题在VLSI，制造业，批量购买的商品集等等中都有应用。 对问题的理论洞察力很可能会更好地理解问题。