AF: Small: New Directions in Network Design

AF：小型：网络设计的新方向

• 批准号: 2228995
• 负责人: Michael Dinitz
• 金额: $ 56.8万
• 依托单位: Johns Hopkins University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2022
• 资助国家: 美国
• 起止时间: 2022-11-01 至 2025-10-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2228995&HistoricalAwards=false
• 关键词: AF; Small; New; Directions; Network

Network design, where one attempts to build graphs that optimize some objective function subject to some constraints, is a central task in computer science. Algorithmic problems involving network design arise in many different settings, ranging from designing computer networks to sparsifying big data. Given its importance, network design has been the subject of extensive study, and an enormous amount is already known. However, as technology and society evolve, new network design problems become important. These are often variants of previous well-studied problems but require new models, techniques, and ideas. This project involves studying some of these new problems. In particular, this project includes problems about designing large-scale computer networks that utilize new reconfigurable technologies; problems about taking classical objects that are not network-design problems and looking at them through a network design lens, increasing their practical utility; and problems that focus on taking old network design problems and studying more flexible variants to make them useful in more modern settings. This project also incorporates mentoring and including underrepresented undergraduates and high school students in the more applied aspects of this work and outreach to middle schools in Baltimore through existing mathematics-based programs.In more detail, this project involves three new directions for network design that have not previously been seriously studied but are theoretically and practically important. First: problems that previously had no application but, due to the advent of new technologies, are now extremely important in actual applications while also being theoretically natural. This project focuses on demand-aware network topology design, which involves intriguing new theoretical problems motivated by advances in networking technology. Second: optimizing graph-theoretic objects and data structures that are usually thought of as extremal. In particular, this project includes studying optimization versions of geometric spanners, emulators, distance oracles, and spectral sparsifiers. Third: new objective functions for classical problems. The main example of this is classical network design problems (spanning tree, Steiner tree, etc.) where the new objective is the p-norm of the degree vector, generalizing and interpolating between the classical objectives of the total number of edges (the 1-norm) and the maximum degree (the infinity-norm). The p-norm is a standard objective in other parts of algorithms but has not previously been considered in network design. Studying intermediate norms will allow the algorithm user to use a single knob to interpolate between global density (the 1-norm) and local density (the infinity-norm).This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

网络设计，试图构建优化某些目标功能受到某些约束的图表是计算机科学的核心任务。涉及网络设计的算法问题在许多不同的设置中出现，从设计计算机网络到稀疏大数据。鉴于其重要性，网络设计一直是广泛研究的主题，并且已经知道了大量研究。但是，随着技术和社会的发展，新的网络设计问题变得重要。这些通常是以前研究过的问题的变体，但需要新的模型，技术和想法。该项目涉及研究其中一些新问题。特别是，该项目包括设计使用新的可重构技术的大型计算机网络的问题；出现不属于网络设计问题的经典对象并通过网络设计镜头查看它们的问题，从而提高了它们的实际效用；以及专注于处理旧网络设计问题并研究更灵活的变体以使其在更现代的环境中有用的问题。该项目还通过现有基于数学的计划进行了指导，并将其包括代表性不足的本科生和高中生包括在巴尔的摩的中学的更加应用的方面。更详细的详细信息，该项目涉及以前没有认真研究过的三个新的网络设计方向。首先：以前没有应用的问题，但由于新技术的出现，现在在实际应用中非常重要，同时在理论上也很自然。该项目着重于需求感知的网络拓扑设计，该设计涉及引起网络技术进步所激发的新理论问题。第二：优化通常被认为是极端的图理论对象和数据结构。特别是，该项目包括研究几何跨度，仿真器，距离甲骨文和光谱稀疏器的优化版本。第三：经典问题的新目标功能。其中的主要例子是经典的网络设计问题（跨越树，施泰纳树等），其中新的目标是学位矢量的p-norm，在边缘总数（1-元素）和最大程度（Infinity-Norm）的经典目标之间概括和插值。 P-Norm是算法其他部分的标准目标，但以前在网络设计中尚未考虑。研究中间规范将使算法用户可以使用单个旋钮在全球密度（1-Norm）和局部密度（无限范围）之间进行插值。该奖项反映了NSF的法定任务，并被认为是值得通过基金会的知识分子优点和更广泛影响的审查审查标准来通过评估来通过评估来获得支持的。