Geometric Networks

This project has studied geometric networks, which represent intercon» nections between entities that arise in physical domains or geometric spaces. Networks are all around us and are an important part of the technology in our daily lives. Examples of geometric networks include wired / wireless communication networks, transportation systems, power grids, sensor networks, and geometric graphs that arise in information visualization.

Geometric networks often have special structure that allows their anal» ysis and optimization to be done more efficiently than is possible in general (non-geometric) networks. A classic example of such a problem is the com» putation of a minimum spanning tree (MST): In the Euclidean setting, fast exact and approximate methods are possible based on the special structure of Euclidean networks (e. g., that a planar MST is a subgraph of the linear-size Delaunay graph). Another class of examples includes the notoriously hard (NP—hard) optimization problems of computing a minimum-weight Steiner spanning tI'ee (MSST) or a minimum—cost traveling salesman (TSP) tour. While it is known, e.g., that computing a nearly optimal TSP tour in general metrics/ networks is hard, the special structure that comes from geometric embeddings has allowed for the discovery of polynomial time approximation schemes (PTAS’s) for a variety of geometric network optimization problems, including the TSP and the MSST.

In this project, we have broadly studied geometric network optimization problems that arise in application areas that include wireless communica» tion (scheduling wireless communication in the presence of noise), recharg» ing station placement for electric vehicles, and optimization problems that involve “choice” together with network optimization and/or coverage. Fun» damental results on the complexity of these problems have been obtained and published. Results include also approximation algorithms that exploit the special structure of the geometric data. The techniques and results are of significance in the study of algorithms and should find applications in a variety of related fields in which network optimization problems arise.

The results were obtained through a close collaboration among the Israeli and American scientists and their students, through reciprocal visits and face—to—face meetings at conferences and workshops.