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.
