AF: Small: Looking Under Rocks: A Search for a Provably Stronger TSP Relaxation
AF:小:寻找岩石下:寻找可证明更强的 TSP 弛豫
基本信息
- 批准号:1908517
- 负责人:
- 金额:$ 10.56万
- 依托单位:
- 依托单位国家:美国
- 项目类别:Standard Grant
- 财政年份:2019
- 资助国家:美国
- 起止时间:2019-10-01 至 2021-09-30
- 项目状态:已结题
- 来源:
- 关键词:
项目摘要
The traveling salesman problem is one of the most widely known problems of computational difficulty. The goal of the problem is to find the cheapest route for a salesman to visit a number of cities and return to home. It is not known whether there is a means of finding the best possible tour short of enumerating the exponentially large number of possible tours. Widely used algorithms for finding the best possible solution involve computing lower bounds on the length of the tour, and the closer the bound is to cost of the best possible tour, the quicker these algorithms run. This project will investigate alternative lower bounds for the traveling salesman problem to the ones widely used in practice, in the hopes of finding a provably better lower bound. A better understanding of lower bounds for the traveling salesman problem should help with solving other computationally difficult problems. The traveling salesman problem is one that is easy to explain to undergraduates and high school students. The PI and his graduate student plan to use their research as a means of outreach to such students, and to involve undergraduates in their project.Current methods for computing the optimal solution to the traveling salesman problem involve repeatedly solving a well-known linear programming relaxation of the problem. Although this bound is extremely good in practice (that is, it is very close to value of an optimal solution), its worst-case behavior is not well understood, despite decades of research. This project intends to study alternative lower bounds for the traveling salesman problem: it will start by studying semidefinite programming relaxations of the problem, and also consider other constraints that might be added to the linear program in order to be able to prove stronger statements about its worst-case behavior than are currently known. In addition, the project will consider some variants of the traveling salesman problem that have not been as well-studied, including the circulant TSP; for this variant, we are not even sure if the problem is NP-hard or has a polynomial-time algorithm.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.
旅行商问题是最广为人知的计算难度问题之一。该问题的目标是为推销员找到访问多个城市并返回家乡的最便宜的路线。目前尚不清楚是否有一种方法可以在不枚举数量呈指数级增长的可能旅行的情况下找到最佳可能的旅行。用于寻找最佳可能解决方案的广泛使用的算法涉及计算旅行长度的下限,并且下限越接近最佳可能旅行的成本,这些算法运行得越快。该项目将研究旅行商问题的替代下界,以替代实践中广泛使用的下界,希望找到一个可证明更好的下界。更好地理解旅行商问题的下界应该有助于解决其他计算困难的问题。旅行商问题是一个很容易向本科生和高中生解释的问题。 PI 和他的研究生计划利用他们的研究作为接触这些学生的一种手段,并让本科生参与他们的项目。当前计算旅行商问题最优解的方法涉及重复求解著名的线性规划松弛的问题。尽管这个界限在实践中非常好(也就是说,它非常接近最优解决方案的值),但尽管经过了数十年的研究,它的最坏情况行为仍然没有得到很好的理解。该项目打算研究旅行商问题的替代下界:它将首先研究问题的半定规划松弛,并考虑可能添加到线性规划中的其他约束,以便能够证明关于其的更强的陈述比目前已知的最坏情况的行为。 此外,该项目还将考虑旅行商问题的一些尚未得到充分研究的变体,包括循环 TSP;对于这个变体,我们甚至不确定问题是否是 NP 难问题或具有多项式时间算法。该奖项反映了 NSF 的法定使命,并通过使用基金会的智力价值和更广泛的影响审查标准进行评估,被认为值得支持。
项目成果
期刊论文数量(4)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
Subtour elimination constraints imply a matrix-tree theorem SDP constraint for the TSP
子巡回消除约束意味着 TSP 的矩阵树定理 SDP 约束
- DOI:10.1016/j.orl.2020.02.011
- 发表时间:2020-05
- 期刊:
- 影响因子:1.1
- 作者:Gutekunst, Samuel C.;Williamson, David P.
- 通讯作者:Williamson, David P.
Characterizing the Integrality Gap of the Subtour LP for the Circulant Traveling Salesman Problem
描述循环旅行商问题的 Subtour LP 的完整性差距
- DOI:10.1137/19m1245840
- 发表时间:2019-01
- 期刊:
- 影响因子:0.8
- 作者:Gutekunst, Samuel C.;Williamson, David P.
- 通讯作者:Williamson, David P.
Semidefinite Programming Relaxations of the Traveling Salesman Problem and Their Integrality Gaps
旅行商问题的半定规划松弛及其完整性差距
- DOI:10.1287/moor.2020.1100
- 发表时间:2021-07
- 期刊:
- 影响因子:1.7
- 作者:Gutekunst, Samuel C.;Williamson, David P.
- 通讯作者:Williamson, David P.
The Unbounded Integrality Gap of a Semidefinite Relaxation of the Traveling Salesman Problem
旅行商问题半定松弛的无界积分间隙
- DOI:10.1137/17m1154722
- 发表时间:2018-01
- 期刊:
- 影响因子:3.1
- 作者:Gutekunst, Samuel C.;Williamson, David P.
- 通讯作者:Williamson, David P.
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
数据更新时间:{{ journalArticles.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ monograph.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ sciAawards.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ conferencePapers.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ patent.updateTime }}
David Williamson其他文献
The PROMISING Project: A Pilot Study to Improve Geriatric Care Through a Pharmacist-Led Psychotropic Stewardship Program
有前途的项目:通过药剂师主导的精神药物管理计划改善老年护理的试点研究
- DOI:
- 发表时间:
2023 - 期刊:
- 影响因子:2.8
- 作者:
Marie d'Amours;Farah Ettis;Lauriane Ginefri;Johnny Lim;Angela;Jennifer Fontaine;Dana Wazzan;David Williamson;Vincent Dagenais - 通讯作者:
Vincent Dagenais
Association Between Pupil Light Reflex and Delirium in Adults With Traumatic Brain Injury: Preliminary Findings.
成人创伤性脑损伤的瞳孔光反射与谵妄之间的关联:初步发现。
- DOI:
- 发表时间:
2024 - 期刊:
- 影响因子:2.3
- 作者:
Alexandra Lapierre;Annie Proulx;Céline Gélinas;Stéphanie Dollé;Sheila Alexander;David Williamson;Francis Bernard;C. Arbour - 通讯作者:
C. Arbour
Factor V Cambridge: a new mutation (Arg306-->Thr) associated with resistance to activated protein C.
剑桥因子 V:与活化蛋白 C 抗性相关的新突变 (Arg306-->Thr)。
- DOI:
- 发表时间:
1998 - 期刊:
- 影响因子:20.3
- 作者:
David Williamson;K. Brown;R. Luddington;C. Baglin;Trevor Baglin - 通讯作者:
Trevor Baglin
Model Re-Estimation: An Alternative for Poor Predictive Performance during External Evaluations? Example of Gentamicin in Critically Ill Patients
模型重新估计:外部评估期间预测性能不佳的替代方案?
- DOI:
- 发表时间:
2022 - 期刊:
- 影响因子:5.4
- 作者:
Alexandre Duong;C. Simard;David Williamson;A. Marsot - 通讯作者:
A. Marsot
Effects of OROS Methylphenidate on Academic, Behavioral, and Cognitive Tasks in Children 9 to 12 Years of Age With Attention-Deficit/Hyperactivity Disorder
OROS 哌醋甲酯对 9 至 12 岁注意力缺陷/多动症儿童学业、行为和认知任务的影响
- DOI:
10.1177/0009922810394832 - 发表时间:
2011-04-01 - 期刊:
- 影响因子:1.6
- 作者:
D. Murray;A. Childress;J. Giblin;David Williamson;Robert B. Armstrong;H. Starr - 通讯作者:
H. Starr
David Williamson的其他文献
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
{{ truncateString('David Williamson', 18)}}的其他基金
AF: SMALL: Topics in Bridging Continuous and Discrete Optimization
AF:SMALL:桥接连续优化和离散优化的主题
- 批准号:
2007009 - 财政年份:2020
- 资助金额:
$ 10.56万 - 项目类别:
Standard Grant
AF: EAGER: Approximation algorithms for the traveling salesman problem
AF:EAGER:旅行商问题的近似算法
- 批准号:
1552831 - 财政年份:2015
- 资助金额:
$ 10.56万 - 项目类别:
Standard Grant
AF: Small: The Traveling Salesman Problem and Lightweight Approximation Algorithms
AF:小:旅行商问题和轻量级近似算法
- 批准号:
1115256 - 财政年份:2011
- 资助金额:
$ 10.56万 - 项目类别:
Standard Grant
Contemporary Issues in Network Design
网络设计的当代问题
- 批准号:
0830519 - 财政年份:2008
- 资助金额:
$ 10.56万 - 项目类别:
Standard Grant
Resolving Anomalies in Approximation Algorithms
解决近似算法中的异常
- 批准号:
0514628 - 财政年份:2005
- 资助金额:
$ 10.56万 - 项目类别:
Continuing Grant
Mathematical Sciences:Postdoctoral Research Fellowship
数学科学:博士后研究奖学金
- 批准号:
9305954 - 财政年份:1993
- 资助金额:
$ 10.56万 - 项目类别:
Fellowship Award
Interdisciplinary Research on a Watershed- Estuarine System Of the Chesapeake Bay
切萨皮克湾流域-河口系统的跨学科研究
- 批准号:
7203361 - 财政年份:1971
- 资助金额:
$ 10.56万 - 项目类别:
Interagency Agreement
相似国自然基金
ALKBH5介导的SOCS3-m6A去甲基化修饰在颅脑损伤后小胶质细胞炎性激活中的调控作用及机制研究
- 批准号:82301557
- 批准年份:2023
- 资助金额:30 万元
- 项目类别:青年科学基金项目
miRNA前体小肽miPEP在葡萄低温胁迫抗性中的功能研究
- 批准号:
- 批准年份:2023
- 资助金额:50 万元
- 项目类别:
PKM2苏木化修饰调节非小细胞肺癌起始细胞介导的耐药生态位的机制研究
- 批准号:82372852
- 批准年份:2023
- 资助金额:49 万元
- 项目类别:面上项目
基于翻译组学理论探究LncRNA H19编码多肽PELRM促进小胶质细胞活化介导电针巨刺改善膝关节术后疼痛的机制研究
- 批准号:82305399
- 批准年份:2023
- 资助金额:30 万元
- 项目类别:青年科学基金项目
CLDN6高表达肿瘤细胞亚群在非小细胞肺癌ICB治疗抗性形成中的作用及机制研究
- 批准号:82373364
- 批准年份:2023
- 资助金额:49 万元
- 项目类别:面上项目
相似海外基金
Powering Small Craft with a Novel Ammonia Engine
用新型氨发动机为小型船只提供动力
- 批准号:
10099896 - 财政年份:2024
- 资助金额:
$ 10.56万 - 项目类别:
Collaborative R&D
Protection of quantum information in small clusters of qubits
保护小量子位簇中的量子信息
- 批准号:
EP/Z000572/1 - 财政年份:2024
- 资助金额:
$ 10.56万 - 项目类别:
Research Grant
Designing, simulating, fabricating, and characterising small-pitch LGAD sensors with precise timing
设计、模拟、制造和表征具有精确定时的小间距 LGAD 传感器
- 批准号:
ST/X005194/1 - 财政年份:2024
- 资助金额:
$ 10.56万 - 项目类别:
Training Grant
Identifying causal pathways in cerebral small vessel disease
确定脑小血管疾病的因果途径
- 批准号:
MR/Y014634/1 - 财政年份:2024
- 资助金额:
$ 10.56万 - 项目类别:
Research Grant
Optimisation of small molecule inhibitors for effective targeting of phospholipase C gamma in T-cell lymphoma
优化小分子抑制剂以有效靶向 T 细胞淋巴瘤中的磷脂酶 C γ
- 批准号:
MR/Y503344/1 - 财政年份:2024
- 资助金额:
$ 10.56万 - 项目类别:
Research Grant