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计划在罗格斯-卡姆登大学最近成立的计算机科学本科研究学院的学生的帮助下，在实际环境中测试一些开发的算法。该项目将特别关注NP-hard网络设计问题的近似性，包括一些最重要的连通性问题：有向斯坦纳树、有向斯坦纳森林、群斯坦纳树、多商品批量购买、最小平衡树、树增强、有向根2存活网络和最小成本顶点k连接子图问题。