RUI: Optimization on Geometric Spanner Networks from a Combinatorial Perspective

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