CRII: AF: RUI: Breaking Ground on Circulant TSP

该奖项全部或部分由《2021年美国救援计划法案》（公法117-2）资助。旅行商问题（TSP）是理论计算机科学中最著名的问题之一。它的起源看似简单：销售人员需要访问一系列城市（每个城市在一个周期中只访问一次，从一个家庭办公室开始和结束），并希望找到最便宜的方式来实现这一目标。尽管有这些简单的起源，但它有重要的应用，从制造电路到理解蛋白质-蛋白质相互作用，对TSP的研究推动了整个更广泛的算法研究界的进步。本课题关注的是TSP的一个重要特例——循环旅行商问题（Circulant TSP）。这种特殊情况最早是在20世纪70年代由可重构网络设计和浪费最小化的应用，循环TSP的固有硬度经常被引用为TSP研究中的一个重要问题。该项目建议利用最近的循环TSP结果，并开发一种新的方法来研究循环TSP，有可能解决长期存在的开放性问题。此外，TSP的臭名昭著和简洁的声明使其成为一个引人入胜的问题，用于外展。该项目将培养和支持本科生成为理论计算机科学的研究人员，并将为高中生提供一门新的短期课程，展示TSP的现代研究。更详细地说，TSP是一个众所周知的、形式上的难题。因此，最近一些最令人兴奋的TSP结果源于对特殊的、更结构化的TSP病例的研究。本项目提出了一种新的方法来处理这种特殊情况，循环TSP。在循环TSP中，城市间旅行的投入成本必须特别结构化（具体来说，它们必须表现出一种循环对称）。基本的开放性问题围绕着循环TSP的复杂性。提出的方法来解决这些问题的桥梁技术从多面体组合和数论。具体来说，它侧重于使用这些技术来描述可以放在一起形成TSP可行解的边长度组合（即，访问每个输入城市的哈密顿循环正好一次）。由于这些技术明确地关注于理解可行的TSP解决方案的边长度，它们可能会扩展到循环TSP之外，并为更广泛的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.