Approximating Network Design Problems on Directed and Undirected Graphs

在有向图和无向图上逼近网络设计问题

• 批准号: 0829959
• 负责人: Guy Kortsarz
• 金额: $ 10万
• 依托单位: Rutgers University Camden
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2009
• 资助国家: 美国
• 起止时间: 2009-02-01 至 2012-01-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0829959&HistoricalAwards=false
• 关键词: Approximating; Network; Design; Problems; Directed

Problems that require communication between among users abound in modern life. Such problems present a collection of users and all possible links among all pairs of users, each link carrying a cost. The links can be directed or undirected (in the undirected case both parties can exchange information along the link). The goal is to select a minimum cost collection of links under some communication constraints. The simplest example of such problem is that every user will be able to send a message to every other user perhaps via a series of links. One of the main goals of this proposal is to understand some of the most fundamental network design problems on directed networks whose exact approximability status remains unclear for a very long time. Directed networks appear frequently when modeling the problem by an undirected network is not enough. Applications for which the networks arising are naturally directed include web related problems, problems in social networks, problems on dynamic (namely changing) links in artificial intelligence and more. A crucial example is the directed Steiner problem that is to connect a set of given terminals (stations, users) to a given root (central command) by directed links at low cost. The intellectual merit of the proposal includes expanding our understanding of the power of approximation algorithms and their limitations. In a more broader context, the project will include the creation of a new graduate course on approximation algorithms in the Computer Science department at Rutgers University, Camden. Students taking the course will be encouraged to undertake research work in this subject, or alternatively, work on a large practical project that will compare the theoretical performance guarantees of approximation algorithms versus their performance in practice.

在现代生活中，用户之间需要沟通的问题。这些问题呈现了所有用户的收集以及所有可能的用户之间的所有可能链接，每个链接都带有成本。链接可以指向或无方向性（在无方便的情况下，双方都可以沿链接交换信息）。目标是在某些通信约束下选择最低链接的成本集合。 此类问题的最简单示例是，每个用户都可以通过一系列链接向其他用户发送消息。 该提案的主要目标之一是了解有指导网络上一些最基本的网络设计问题，这些网络的确切近似性状态在很长一段时间内仍不清楚。 当通过非方向网络对问题进行建模时，有向网络频繁出现是不够的。自然指示的网络引起的应用程序包括与Web相关的问题，社交网络中的问题，动态问题（即改变）人工智能中的链接等等。一个至关重要的例子是导向的Steiner问题，它是将一组给定的终端（站点，用户）连接到以低成本的有向链接到给定的根（中央命令）。该提案的智力优点包括扩展我们对近似算法及其局限性的理解。在更广泛的背景下，该项目将包括在卡姆登（Camden）罗格斯大学（Rutgers University）的计算机科学系中创建新的研究生课程。鼓励参加该课程的学生将在此主题上进行研究工作，或者，或者在一个大型实践项目上工作，该项目将比较近似算法的理论性能保证与在实践中的表现。