CRII: AF: RUI: Breaking Ground on Circulant TSP

点击翻译按钮获取中文摘要

This award is funded in whole or in part under the American Rescue Plan Act of 2021 (Public Law 117-2).The Traveling Salesman Problem (TSP) is one of the most famous problems in theoretical computer science. Its origins are deceptively simple: a salesperson needs to visit a set of cities (visiting each city exactly once in a cycle, starting and ending at a home office) and wants to find the least expensive way to do so. Despite these simple origins, it has important applications ranging from producing circuits to understanding protein-protein interactions, and research on the TSP has fueled progress throughout the broader algorithms research community. This project focuses on an important special case of the TSP known as the Circulant Traveling Salesman Problem (Circulant TSP). This special case was first motivated in the 1970's by applications in reconfigurable network design and waste minimization, and the innate hardness of Circulant TSP has often been cited as an important question in TSP research. This project proposes to capitalize on recent Circulant TSP results, and to develop a new approach to studying Circulant TSP with potential to resolve long-standing open questions. Further, the TSP's notoriety and succinct statement make it an engaging problem for use in outreach. The project will train and support undergraduate students to become researchers in theoretical computer science, and the project will lead to a new short-course for high school students on the TSP showcasing modern research. In more detail, the TSP is a notoriously and formally hard problem. As such, some of the most exciting recent TSP results have stemmed from studying special, more structured cases of the TSP. This project proposes a new approach to one such special case, Circulant TSP. In Circulant TSP, the input costs of travelling between cities have to be particularly structured (specifically, they must exhibit a type of circulant symmetry). Fundamental open questions revolve around the complexity of Circulant TSP. The proposed approach to addressing these questions bridges techniques from polyhedral combinatorics and number theory. Specifically, it focuses on using these techniques to describe the combinations of edge lengths that can be put together to form a feasible solution to the TSP (i.e., a Hamiltonian cycle visiting each of the input cities exactly once). Because these techniques focus explicitly on understanding the edge lengths of feasible TSP solutions, they will likely extend beyond Circulant TSP and contribute to the broader TSP literature.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.