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 范数，在边总数的经典目标之间进行概括和插值（第 1 个目标） -范数）和最大程度（无穷范数）。 p 范数是算法其他部分的标准目标，但之前在网络设计中并未考虑过。研究中间范数将允许算法用户使用单个旋钮在全局密度（1-范数）和局部密度（无穷大范数）之间进行插值。该奖项反映了 NSF 的法定使命，并通过使用评估被认为值得支持基金会的智力价值和更广泛的影响审查标准。