CRII: AF: RUI: Breaking Ground on Circulant TSP

CRII：AF：RUI：循环 TSP 破土动工

• 批准号: 2153331
• 负责人: Samuel Gutekunst
• 金额: $ 15.58万
• 依托单位: Bucknell University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2022
• 资助国家: 美国
• 起止时间: 2022-05-01 至 2025-04-30
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2153331&HistoricalAwards=false
• 关键词: CRII; AF; RUI; Breaking; Ground

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.

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