AF: Small: Rounding by Sampling Method and Applications to Traveling Salesman Problems

Stanford University, Stanford CA

Investigators

Abstract

This project aims to further our understanding of the combinatorial structure of the Traveling Salesman Problem (TSP). It builds on a recent result that reduces asymmetric TSP to finding "thin trees'' in graphs and uses techniques in graph sparsification and metric embedding to develop new algorithms. It also includes the study of a new approximation algorithm for the symmetric TSP proposed by the project's Principal Investigator (PI) which is conjectured to break the 3/2 barrier due to Christofides. The project also advances the rounding-by-sampling method developed by the PI and co-authors, and extends it to design new algorithms for various online and stochastic problems. The proposed problems have applications in network design, online advertising, and power management in electrical networks. The proposed research on TSP has broad applications in logistics, planning, and vehicle routing. The other optimization problems studied in the project have applications ranging from online advertising to transmission and storage of alternative sources of energy. The project also includes a strong education and outreach component including the design of new courses on approximation algorithms and lectures on the subject for a broader audience.