RUI: Optimization on Geometric Spanner Networks from a Combinatorial Perspective

The University Corporation, Northridge, Northridge CA

Investigators

Abstract

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.