BSF:2014163:APPROXIMABILITY OF NETWORK DESIGN PROBLEMS

Project Details

Description

This project aims to derive fundamental results in the field of network design. In network design, one wishes to derive a network which simultaneously has low cost and desirable properties such as high connectivity for fault tolerance. The goal of this project is to find improved approximation algorithms - which find a network with cost and quality provably near the best possible for a given problem instance - or to prove new inapproximability results. Problems in this area have a large practical significance in many areas including transportation planning, road planning, and power grids. The project will provide undergraduate research opportunities. The PI plans to test some of the algorithms developed in practical settings with the assistance of students from the recently launched Computer Science Undergraduate Research Academy at Rutgers-Camden. The project will focus in particular on approximability of NP-hard network design problems including some of the most significant connectivity problems: Directed Steiner Tree, Directed Steiner Forest, Group Steiner Tree, Multicommodity Buy-at-Bulk, Minimum Poise Tree, Tree Augmentation, Directed Rooted 2-Survivable Network, and the Minimum-cost Vertex k-Connected Sub-graph problem.
StatusFinished
Effective start/end date9/1/158/31/19

Funding

  • National Science Foundation (National Science Foundation (NSF))

Fingerprint Explore the research topics touched on by this project. These labels are generated based on the underlying awards/grants. Together they form a unique fingerprint.