Approximating Network Design Problems on Directed and Undirected Graphs

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

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.