CRII: AF: RUI: Breaking Ground on Circulant TSP

该奖项全部或部分由2021年美国救援计划法案（公法117-2）资助。旅行推销员问题（TSP）是理论计算机科学中最著名的问题之一。它的起源看似简单：销售人员需要访问一系列城市（每个城市在一个周期中只访问一次，从家庭办公室开始和结束），并希望找到最便宜的方式。 尽管有这些简单的起源，它有重要的应用，从生产电路到理解蛋白质-蛋白质相互作用，对TSP的研究推动了整个更广泛的算法研究社区的进步。这个项目的重点是一个重要的特殊情况下的TSP称为循环旅行商问题（循环TSP）。 这种特殊的情况首先是在20世纪70年代的可重构网络设计和浪费最小化的应用程序的动机，循环TSP的固有硬度经常被引用作为TSP研究中的一个重要问题。 该项目建议利用最近的循环TSP的结果，并开发一种新的方法来研究循环TSP，有可能解决长期悬而未决的问题。 此外，TSP的恶名和简洁的陈述使其成为一个用于推广的吸引人的问题。 该项目将培训和支持本科生成为理论计算机科学的研究人员，该项目将为高中生提供一个新的TSP短期课程，展示现代研究。 更详细地说，TSP是一个众所周知的形式上的难题。 因此，最近一些最令人兴奋的TSP结果源于研究TSP的特殊，更结构化的情况。 该项目提出了一种新的方法，这样一个特殊的情况下，循环TSP。 在循环TSP中，城市间旅行的投入成本必须是特别结构化的（具体来说，它们必须表现出一种循环对称性）。 基本的开放性问题围绕着循环TSP的复杂性。 提出的方法来解决这些问题的桥梁技术从多面体组合学和数论。 具体地说，它侧重于使用这些技术来描述可以放在一起以形成TSP的可行解的边长度的组合（即，访问每个输入城市恰好一次的哈密尔顿循环）。 由于这些技术明确地侧重于了解可行的TSP解决方案的边长，它们可能会超越循环TSP，并有助于更广泛的TSP literation.This奖项反映了NSF的法定使命，并已被认为是值得通过使用基金会的智力价值和更广泛的影响审查标准进行评估的支持。

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.