Light Spanners for Hard Metrical Optimization Problems

Emory University, Atlanta GA

Investigators

Abstract

Given a metric space, that is a finite set of points with distances between them, there are several classical minimization problems that are hard to solve exactly. A prime example is the traveling salesman problem (TSP), where we want to find a cyclic tour visiting all the points with minimum total distance. These problems arise in a wide range of applications such as manufacturing and communications network design. In the worst case it is NP-hard to solve these problems even approximately, that is with relative error better than some constant threshold. Recent results show that these problems are easier in metric spaces that often arise in practice. In particular if the distances are geometric, or if they are given by shortest paths in a simple graph (such as a planar graph), then the TSP and similar problems have approximation schemes. These schemes run in polynomial or quasi-polynomial time, with the exponent depending on the desired relative error. The main techniques include separators, spanners, and dynamic programming. In particular a spanner is a subgraph of a given graph, whose shortest path metric is a close approximation of the original. In various graph families we can find spanners with a useful tradeoff between the total weight and the relative error. This research continues the development of these techniques, in particular seeking better spanner constructions and possibly some useful lower bounds. One goal of the project is some progress on two unsolved variants: the geometric case in the presence of obstacles, and the graphical case in the presence of many extra ``Steiner'' points.