BSF:2014163:Approximability of network design problems
BSF:2014163:Approximability of network design problems
批准号:
1540547
负责人:
Guy Kortsarz
金额:
$5.0万
依托单位国家:
美国
项目类别:
Standard Grant
财政年份:
2015
资助国家:
美国
项目状态:
已结题
起止时间:
2015-09-01 至 2020-08-31
中文摘要
该项目旨在获得网络设计领域的基本成果。在网络设计中,人们希望得到一个同时具有低成本和期望的特性的网络,例如用于容错的高连通性。这个项目的目标是找到改进的近似算法-找到一个成本和质量都被证明接近给定问题实例的最佳可能的网络-或者证明新的不可逼近结果。这方面的问题在交通规划、道路规划、电网等领域都具有很大的现实意义。该项目将为本科生提供研究机会。PI计划在最近成立的罗格斯大学计算机科学本科生研究院的学生的帮助下,测试一些在实际环境中开发的算法。该项目将特别关注NP-Hard网络设计问题的逼近性,包括一些最重要的连通性问题:有向Steiner树、有向Steiner森林、组Steiner树、多商品批量购买、最小平衡树、树增强、有向有根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.
期刊论文(0)
专著(0)
科研奖励(0)
会议论文
AF: Small: RUI: Network design and facility location problems
-
批准号:1218620
-
项目类别:Standard Grant
-
资助金额:$33.39万
-
财政年份:2012
-
负责人:Guy Kortsarz
-
依托单位:
Approximating Network Design Problems on Directed and Undirected Graphs
-
批准号:0829959
-
项目类别:Standard Grant
-
资助金额:$10.0万
-
财政年份:2009
-
负责人:Guy Kortsarz
-
依托单位:
Approximating Bicriteria Network-Design Problems
-
批准号:0728787
-
项目类别:Standard Grant
-
资助金额:$5.79万
-
财政年份:2008
-
负责人:Guy Kortsarz
-
依托单位: