EAPSI: Designing Network Infrastructure for Efficient Data Distribution

Iglesias Jennifer M, Pittsburgh PA

Investigators

Abstract

Terminals are places that want to either send or receive information. The problem is to build networks for every terminal so that every one of them is able to send or receive all the necessary information. The goal of the project is to develop an algorithm which finds low cost networks meeting all the necessary demands of the terminals. In this problem, we will focus on minimizing operation costs as opposed to minimizing installation costs. This view of costs is a significant shift from how the problem has previously been studied. In order to better investigate this problem, I will go to Japan to work with Dr. Takuro Fukunaga at the National Institute for Informatics. Dr. Fukunaga has previous worked on various related problems with the costs based on upkeep and developed novel approaches for solving them. The node weighted design of overlapping networks problem (DON) is a network design problem where a core graph with node weights and a demand graph between pairs of terminals are given. The goal is to build connected networks for each terminal of total minimum cost such that all demands are satisfied. A demand for a pair (s,t) is satisfied if there is a node which is in both s's network and t's network. An edge is in a network if both of its nodes are in the network. The total cost is the sum of all the networks; in particular if some node is in multiple networks it will be counted multiple times. Previous work on this problem has studied the edge weighted version, in the cases of a complete bipartite demand graph and a general demand graph. The goal of the summer is to develop approximation algorithms for node weighted DON, and find lower bounds based on hardness. This award under the East Asia and Pacific Summer Institutes program supports summer research by a U.S. graduate student and is jointly funded by NSF and the Japan Society for the Promotion of Science.