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.

在现代生活中，需要用户之间进行通信的问题比比皆是。这样的问题提出了一个用户的集合和所有用户对之间的所有可能的链接，每个链接都有成本。链接可以是有向的或无向的（在无向的情况下，双方可以沿着链接交换信息）。我们的目标是选择一个最小的成本收集下的一些通信约束的链接。 这种问题最简单的例子是，每个用户都可以通过一系列链接向其他用户发送消息。 这个建议的主要目标之一是了解一些最基本的网络设计问题的有向网络，其确切的逼近状态仍然不清楚很长一段时间。 当用无向网络对问题建模不够时，有向网络就经常出现。网络产生的应用包括网络相关问题、社交网络中的问题、人工智能中的动态（即变化）链接问题等等。一个重要的例子是有向斯坦纳问题，即通过有向链路以低成本将一组给定的终端（站，用户）连接到给定的根（中央命令）。该提案的智力价值包括扩大我们对近似算法的能力及其局限性的理解。在更广泛的范围内，该项目将包括在卡姆登罗格斯大学计算机科学系开设一门关于近似算法的新的研究生课程。将鼓励学生参加本课程的研究工作，或者在一个大型的实际项目中工作，该项目将比较近似算法的理论性能保证与其在实践中的性能。