AF: Small: New Approaches to Fundamental Problems in Network Design

AF：小：网络设计中基本问题的新方法

• 批准号: 1115849
• 负责人: Michel Goemans
• 金额: $ 45万
• 依托单位: Massachusetts Institute of Technology
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2011
• 资助国家: 美国
• 起止时间: 2011-07-01 至 2015-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1115849&HistoricalAwards=false
• 关键词: AF; Small; New; Approaches; Fundamental

Networks, of all kinds, surround us in our modern existence. Telecommunications networks, road networks, social networks, flight connections, and even the circuits in the microprocessors in our computers and cellphones are just a few examples. Some fundamental network problems appear again and again in a variety of these settings, and better algorithms - and more importantly, keener insights - into these problems are needed. Many of these problems are algorithmically hard optimization problems, and we cannot expect optimal solutions in reasonable time. Instead, approximations must be accepted, and the aim is to provide the best possible guarantee efficiently.The goal of this project is to explore new approaches and techniques for fundamental optimization problems, both new and old, in network design. The problems to be investigated include the classical traveling salesman problem, the problem of finding a tour of minimum length visiting all the nodes in a network, and the Steiner tree problem, which asks for the cheapest tree connecting some collection of terminals within a network. These problems have been intensively studied, but recently there has been some exciting progress. Two main techniques underlying this progress are the study of "thin" spanning trees, and advances in the design of strong rounding algorithms. In this project, the PIs aim to continue investigation in these directions with the hope of further breakthroughs. Another class of problems we consider relates to the quite practical issue of provisioning a network to handle varied and uncertain demands. This context has already demonstrated a combination of beautiful mathematical structure and important practical implications, and one of the goals of this project is to expand the class of such network design problems that can be efficiently solved.Due to their fundamental nature, progress on these problems would have an immediate impact on the field, driving even further progress. There would also be a broader impact, with theoretical advancements aiding and guiding practical improvements in industry. In particular, part of the project will focus on recent models of demand patterns and capacity requirements in telecommunication networks. As bandwidth requirements increase rapidly, with the dramatic increase in video and multimedia, ways need to be found to more efficiently utilize network resources. Another central aspect of this project with broader impact is the training and mentoring of graduate students and junior researchers.

各种各样的网络在我们的现代生活中围绕着我们。电信网络、道路网络、社交网络、航班连接，甚至我们的电脑和手机中的微处理器电路只是几个例子。一些基本的网络问题在各种各样的环境中一次又一次地出现，需要更好的算法--更重要的是，需要对这些问题有更敏锐的洞察力。这些问题中的许多是算法上困难的优化问题，我们不能期望在合理的时间内得到最优解。相反，近似值必须被接受，目的是提供最好的保证有效。这个项目的目标是探索新的方法和技术的基本优化问题，新的和旧的，在网络设计。要研究的问题包括经典的旅行推销员问题，找到一个最小长度的旅游访问网络中的所有节点的问题，和Steiner树问题，它要求最便宜的树连接网络中的一些终端的集合。这些问题已经被深入研究，但最近有一些令人兴奋的进展。 这一进展的两个主要技术基础是“瘦”生成树的研究，并在强舍入算法的设计进展。 在这个项目中，PI的目标是继续在这些方向的研究，希望进一步突破。我们考虑的另一类问题涉及到相当实际的问题，即提供一个网络来处理各种不确定的需求。这个背景已经展示了美丽的数学结构和重要的实际意义的结合，这个项目的目标之一是扩大这类网络设计问题，可以有效地解决。由于其基本性质，这些问题的进展将对该领域产生直接影响，推动进一步的进展。 这也将产生更广泛的影响，理论上的进步将帮助和指导工业的实际改进。特别是，该项目的一部分将侧重于电信网络需求模式和能力要求的最新模型。随着带宽需求的快速增长，视频和多媒体的急剧增加，需要找到更有效地利用网络资源的方法。该项目的另一个具有广泛影响的核心方面是对研究生和初级研究人员的培训和指导。