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.

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