Skip Navigation Links

Project Information

BSF:2014163:APPROXIMABILITY OF NETWORK DESIGN PROBLEMS

Agency:
NSF

National Science Foundation

Project Number:
1540547
Contact PI / Project Leader:
KORTSARZ, GUY
Awardee Organization:
RUTGERS THE STATE UNIVERSITY OF NEW JERSEY CAMDEN

Description

Abstract Text:
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.
Project Terms:
Academy; Algorithms; Area; computer science; cost; design; forest; Goals; Graph; improved; Plant Roots; Property; Students; Testing; Transportation; Trees; undergraduate research

Details

Contact PI / Project Leader Information:
Name:  KORTSARZ, GUY
Other PI Information:
Not Applicable
Awardee Organization:
Name:  RUTGERS THE STATE UNIVERSITY OF NEW JERSEY CAMDEN
City:  CAMDEN    
Country:  UNITED STATES
Congressional District:
State Code:  NJ
District:  01
Other Information:
Fiscal Year: 2015
Award Notice Date: 06-Aug-2015
DUNS Number: 625216556
Project Start Date: 01-Sep-2015
Budget Start Date:
CFDA Code: 47.070
Project End Date: 31-Aug-2019
Budget End Date:
Agency: ?

Agency: The entity responsible for the administering of a research grant, project, or contract. This may represent a federal department, agency, or sub-agency (institute or center). Details on agencies in Federal RePORTER can be found in the FAQ page.

National Science Foundation
Project Funding Information for 2015:
Year Agency

Agency: The entity responsible for the administering of a research grant, project, or contract. This may represent a federal department, agency, or sub-agency (institute or center). Details on agencies in Federal RePORTER can be found in the FAQ page.

FY Total Cost
2015 NSF

National Science Foundation

$50,000

Results

i

It is important to recognize, and consider in any interpretation of Federal RePORTER data, that the publication and patent information cannot be associated with any particular year of a research project. The lag between research being conducted and the availability of its results in a publication or patent award varies substantially. For that reason, it's difficult, if not impossible, to associate a publication or patent with any specific year of the project. Likewise, it is not possible to associate a publication or patent with any particular supplement to a research project or a particular subproject of a multi-project grant.

ABOUT FEDERAL REPORTER RESULTS

Publications: i

Click on the column header to sort the results

PubMed = PubMed PubMed Central = PubMed Central Google Scholar = Google Scholar

Patents: i

Click on the column header to sort the results

Similar Projects

Download Adobe Acrobat Reader:Adobe Acrobat VERSION: 3.41.0 Release Notes
Back to Top