BSF:2014163:Approximability of network design problems

该项目旨在获得网络设计领域的基本成果。 在网络设计中，人们希望得到一个网络，同时具有低成本和理想的属性，如高连通性的容错。 这个项目的目标是找到改进的近似算法-找到一个网络的成本和质量可证明接近最好的可能为给定的问题实例-或证明新的不可近似的结果。 这一领域的问题在交通规划、道路规划、电网规划等诸多领域都具有很大的现实意义。 该项目将提供本科生的研究机会。 PI计划在Rutgers-Camden最近成立的计算机科学本科研究院的学生的帮助下，在实际环境中测试一些开发的算法。该项目将特别关注NP-hard网络设计问题的可逼近性，包括一些最重要的连接问题：有向Steiner树，有向Steiner森林，Group Steiner树，多商品批量购买，最小Poise树，树扩充，有向有根2-生存网络，最小代价顶点k连通子图问题

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.