BSF:2014163:Approximability of network design problems

BSF:2014163:网络设计问题的近似性

• 批准号: 1540547
• 负责人: Guy Kortsarz
• 金额: $ 5万
• 依托单位: Rutgers University Camden
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2015
• 资助国家: 美国
• 起止时间: 2015-09-01 至 2020-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1540547&HistoricalAwards=false
• 关键词: BSF; 2014163; Approximability; network; design

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.

该项目旨在在网络设计领域获得基本结果。 在网络设计中，人们希望得出一个网络，该网络同时具有低成本和理想的属性，例如高连接性的容错连接性。 该项目的目的是找到改进的近似算法 - 该算法找到了一个具有成本和质量的网络，证明是给定问题实例的最佳选择 - 或证明了新的不可耐性结果。 该领域的问题在许多领域具有很大的实际意义，包括运输规划，道路规划和电网。 该项目将提供本科研究机会。 PI计划在最近发射的计算机科学本科本科生研究学院的协助下测试在实际情况下开发的一些算法扎根的2节感受网络，以及最低成本的顶点k连接子图问题。