RUI: Optimization on Geometric Spanner Networks from a Combinatorial Perspective

生产、处理和理解大数据是我们日常生活的一部分。图论经常被用来对数据项之间的关系进行建模。然而，对于大而密集的图，保持所有顶点对之间的成对距离在计算上是困难的。扳手是一种稀疏子结构，它近似于原始网络中的距离--近似比称为拉伸因子。在实践和理论中，扳手越来越多地被用于有效地表示顶点之间的距离。它们在几何环境中的表现尤其令人印象深刻，在几何环境中，拉伸系数可以任意接近于1。在过去的几年里，计算的最新结果在开发高效算法方面取得了重大进展，并提出了关于几何扳手的最小重量、尺寸和直径关于其拉伸因子的渐近行为的新的组合问题。这个项目将从组合的角度研究几何扳手的优化。本科生和研究生的参与将有助于培养一支熟悉大型图的渐近行为的高技能劳动力，并为应对数据驱动的社会中的新挑战做好准备。本项目从极值组合学的角度研究了几个与几何扳手网络密切相关的问题。一组问题涉及当拉伸因子趋于1时扳手的渐近行为。它的目的是在几何场景中确定T扳手的最小重量与n个点的拉伸因子t的依赖关系：在d维单位立方体中，在具有加倍维度d的空间中，或者在整数格的一部分中。它将探索扳手的图形直径与其最小重量、稀疏度或重量之间的权衡。当Steiner点被允许时，Steiner点的数量和其他优化标准之间的权衡也是非常有趣的。另一组问题涉及几何对象的交叉图的扳手，这与无线网络设计中的应用相关。该项目旨在为d-空间中的球、超矩形和其他几何对象的交叉图，对于较小的t值，推导出t-spanner的最小尺寸的上下界。对接近最佳扳手的行为和可行扳手在各种参数设置下的局限性的新见解将指导高效近似算法的开发。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

Producing, processing, and making sense of large data is part of our everyday life. Graph theory is often called upon for modeling relations between data items. However, for large and dense graphs, maintaining pairwise distances between all pairs of vertices would be computationally prohibitive. A spanner is a sparse substructure that approximates distances in the original network—the approximation ratio is called the stretch factor. Spanners have increasingly been used for the efficient representation of distances between vertices in both practice and theory. Their performance is particularly impressive in geometric settings, where the stretch factor can be arbitrarily close to one. Recent results in computing have made significant progress in developing efficient algorithms over the last few years and raised new combinatorial questions about the asymptotic behavior of the minimum weight, size, and diameter of a geometric spanner in terms of its stretch factor. This project will study optimization on geometric spanners from a combinatorial standpoint. The involvement of undergraduate and graduate students in the project will contribute to training a highly skilled workforce familiar with the asymptotic behavior of large graphs and prepared to tackle new challenges in our data-driven society.This project studies several closely related questions concerning geometric spanner networks from the perspective of extremal combinatorics. One group of questions involves the asymptotic behavior of spanners as the stretch factor tends to one. It aims to determine the dependence of the minimum weight of a t-spanner on the stretch factor t for n points in geometric scenarios: in a d-dimensional unit cube, in spaces with doubling dimension d, or in a section of the integer lattice. It will explore tradeoffs between the graph-diameter of a spanner and its minimum lightness, sparsity, or weight. When Steiner points are allowed, tradeoffs between the number of Steiner points and other optimization criteria are also of great interest. Another group of questions involves spanners for intersection graphs of geometric objects, which are relevant in applications in wireless network design. The project aims to derive upper and lower bounds on the minimum size of t-spanners, for small values of t, for the intersection graphs of balls, hyperrectangles, and other geometric objects in d-space. New insights into the behavior of near-optimal spanners and the limitations of feasible spanners under various parameter settings will guide the development of efficient approximation algorithms.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.