Geometric Optimization Problems

Project Details


This project has studied geometric networks, which represent interconnections 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 analysis and optimization to be done more efficiently than is possible in general (non—geometric) networks. A classic example of such a problem is the computation 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 tree (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 arid the MSST.

In this project, we have broadly studied geometric network optimization problems that arise in application areas that include wireless communication (minimum bottleneck spanning trees, balanced connected subgraphs, robust matching and spanning trees, and low communication cost networks) and transportation and vehicle routing (coordinated delivery problems with trucks and drones). Fundamental 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 (up until the beginning of the pandemic) and weekly Zoom meetings (during the pandemic), with email exchanges in between.

Effective start/end date1/01/16 → …


  • United States-Israel Binational Science Foundation (BSF)


Explore the research topics touched on by this project. These labels are generated based on the underlying awards/grants. Together they form a unique fingerprint.