AF: Small: New Directions in Network Design

点击翻译按钮获取中文摘要

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.