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的一个重要特例--循环旅行商问题(Circle Ant TSP)。这一特例最初是由S在20世纪70年代在可重构网络设计和最小化浪费方面的应用而产生的，循环TSP的固有硬度经常被认为是TSP研究中的一个重要问题。该项目建议利用最新的循环TSP结果，并开发一种新的方法来研究循环TSP，有可能解决长期悬而未决的问题。此外，TSP的臭名昭著和简明扼要的声明使其成为推广使用的一个引人入胜的问题。该项目将培养和支持本科生成为理论计算机科学的研究人员，该项目将为高中生提供一个新的关于TSP的短期课程，展示现代研究。更详细地说，TSP是一个臭名昭著的形式上的难题。因此，最近一些最令人兴奋的TSP结果源于对TSP的特殊、更具结构性的案例的研究。本项目针对这种特殊情况--循环TSP问题提出了一种新的解决方法。在循环TSP中，城市间旅行的投入成本必须具有特殊的结构(具体地说，它们必须表现出一种循环对称性)。基本开放问题围绕循环TSP的复杂性展开。提出的解决这些问题的方法连接了多面体组合数学和数论的技术。具体地说，它侧重于使用这些技术来描述可以组合在一起以形成TSP的可行解的边长度的组合(即，哈密顿循环恰好访问每个输入城市一次)。由于这些技术明确地侧重于了解可行的TSP解决方案的边缘长度，它们可能会扩展到循环TSP之外，并对更广泛的TSP文献做出贡献。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。