Approximating Network Design Problems on Directed and Undirected Graphs
Approximating Network Design Problems on Directed and Undirected Graphs
批准号:
0829959
负责人:
Guy Kortsarz
金额:
$10.0万
依托单位国家:
美国
项目类别:
Standard Grant
财政年份:
2009
资助国家:
美国
项目状态:
已结题
起止时间:
2009-02-01 至 2012-01-31
中文摘要
在现代生活中,需要用户之间进行沟通的问题比比皆是。这样的问题呈现了一组用户和所有用户对之间的所有可能的链路,每条链路都有成本。链接可以是定向的,也可以是非定向的(在非定向的情况下,双方都可以沿着链路交换信息)。目标是在一定的通信约束下选择最小成本的链路集合。这类问题最简单的例子是,每个用户都将能够通过一系列链接向其他每个用户发送消息。这个建议的主要目标之一是了解有向网络上的一些最基本的网络设计问题,这些有向网络的确切可逼近状态在很长一段时间内都不清楚。当用无向网络对问题进行建模时,有向网络频繁出现。网络的产生自然针对的应用包括与网络相关的问题、社交网络中的问题、人工智能中动态(即变化的)链接的问题等等。一个关键的例子是有向Steiner问题,即以低成本通过有向链路将一组给定的终端(站、用户)连接到给定的根(中央命令)。该提议的智力价值包括扩大我们对近似算法的能力及其局限性的理解。在更广泛的背景下,该项目将包括在卡姆登罗格斯大学计算机科学系开设一门关于近似算法的新研究生课程。选修这门课程的学生将被鼓励从事这一主题的研究工作,或者,从事一个大型实践项目,比较近似算法的理论性能保证与它们在实践中的性能。
英文摘要
Problems that require communication between among users abound in modern life. Such problems present a collection of users and all possible links among all pairs of users, each link carrying a cost. The links can be directed or undirected (in the undirected case both parties can exchange information along the link). The goal is to select a minimum cost collection of links under some communication constraints. The simplest example of such problem is that every user will be able to send a message to every other user perhaps via a series of links. One of the main goals of this proposal is to understand some of the most fundamental network design problems on directed networks whose exact approximability status remains unclear for a very long time. Directed networks appear frequently when modeling the problem by an undirected network is not enough. Applications for which the networks arising are naturally directed include web related problems, problems in social networks, problems on dynamic (namely changing) links in artificial intelligence and more. A crucial example is the directed Steiner problem that is to connect a set of given terminals (stations, users) to a given root (central command) by directed links at low cost. The intellectual merit of the proposal includes expanding our understanding of the power of approximation algorithms and their limitations. In a more broader context, the project will include the creation of a new graduate course on approximation algorithms in the Computer Science department at Rutgers University, Camden. Students taking the course will be encouraged to undertake research work in this subject, or alternatively, work on a large practical project that will compare the theoretical performance guarantees of approximation algorithms versus their performance in practice.
期刊论文(0)
专著(0)
科研奖励(0)
会议论文
BSF:2014163:Approximability of network design problems
-
批准号:1540547
-
项目类别:Standard Grant
-
资助金额:$5.0万
-
财政年份:2015
-
负责人:Guy Kortsarz
-
依托单位:
AF: Small: RUI: Network design and facility location problems
-
批准号:1218620
-
项目类别:Standard Grant
-
资助金额:$33.39万
-
财政年份:2012
-
负责人:Guy Kortsarz
-
依托单位:
Approximating Bicriteria Network-Design Problems
-
批准号:0728787
-
项目类别:Standard Grant
-
资助金额:$5.79万
-
财政年份:2008
-
负责人:Guy Kortsarz
-
依托单位:
国内基金
海外基金
登录
查看更多内容
XsmiR167为核心的ceRNA network调控文冠果雄花雌蕊败育机制研究
-
批准号:32572006
-
项目类别:面上项目
-
资助金额:50.00万元
-
批准年份:2025
-
负责人:敖妍
-
依托单位:
丝氨酸/甘氨酸/一碳代谢网络(SGOC metabolic network)调控炎症性巨噬细胞活化及脓毒症病理发生的机制研究
-
批准号:81930042
-
项目类别:重点项目
-
资助金额:305.0万元
-
批准年份:2019
-
负责人:王迪
-
依托单位:
多维在线跨语言Calling Network建模及其在可信国家电子税务软件中的实证应用
-
批准号:91418205
-
项目类别:重大研究计划
-
资助金额:170.0万元
-
批准年份:2014
-
负责人:郑庆华
-
依托单位:
基于Wireless Mesh Network的分布式操作系统研究
-
批准号:60673142
-
项目类别:面上项目
-
资助金额:27.0万元
-
批准年份:2006
-
负责人:罗惠琼
-
依托单位: