語系:
繁體中文
English
說明(常見問題)
回圖書館首頁
手機版館藏查詢
登入
回首頁
切換:
標籤
|
MARC模式
|
ISBD
Fantastic Relaxations of the TSP and...
~
Gutekunst, Samuel Christian.
FindBook
Google Book
Amazon
博客來
Fantastic Relaxations of the TSP and How to Bound Them: Relaxations of the Traveling Salesman Problem and Their Integrality Gaps.
紀錄類型:
書目-電子資源 : Monograph/item
正題名/作者:
Fantastic Relaxations of the TSP and How to Bound Them: Relaxations of the Traveling Salesman Problem and Their Integrality Gaps./
作者:
Gutekunst, Samuel Christian.
出版者:
Ann Arbor : ProQuest Dissertations & Theses, : 2020,
面頁冊數:
170 p.
附註:
Source: Dissertations Abstracts International, Volume: 81-12, Section: B.
Contained By:
Dissertations Abstracts International81-12B.
標題:
Operations research. -
電子資源:
http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=27993667
ISBN:
9798641312880
Fantastic Relaxations of the TSP and How to Bound Them: Relaxations of the Traveling Salesman Problem and Their Integrality Gaps.
Gutekunst, Samuel Christian.
Fantastic Relaxations of the TSP and How to Bound Them: Relaxations of the Traveling Salesman Problem and Their Integrality Gaps.
- Ann Arbor : ProQuest Dissertations & Theses, 2020 - 170 p.
Source: Dissertations Abstracts International, Volume: 81-12, Section: B.
Thesis (Ph.D.)--Cornell University, 2020.
This item must not be sold to any third party vendors.
The Traveling Salesman Problem (TSP) is a fundamental problem in combinatorial optimization, combinatorics, and theoretical computer science and is a canonical NP-hard problem. Given a set of n vertices and pairwise costs cij of traveling between vertices i and j, the TSP asks for a minimum-cost tour visiting each of the vertices exactly once (i.e., a minimum-cost Hamiltonian cycle). Despite the problem's ubiquity, the state-of-the-art TSP approximation algorithm dates back more than 40 years. Its performance guarantee can be derived using a linear program relaxation that is over 50 years old, but the best-known analysis of this linear program's integrality gap (which dictates its use in proving approximation guarantees) has not been improved in nearly 40 years of active research. This thesis contributes to two main avenues of TSP research towards breaking these bottlenecks, both of which involve analyzing TSP relaxations.We first consider relaxations of the TSP that are based on semidefinite programs (SDPs). Recently, many such relaxations have been proposed as avenues towards better approximation algorithms. These SDPs exploit a breadth of mathematical structures and have shown considerable promise in small numerical experiments, but little has been known about their general performance. Our first main results fill this void: we provide the first theoretical analysis of the integrality gap of every major SDP relaxation of the TSP. Specifically, with standard costs that are symmetric and obey the triangle inequality, we show that every major SDP relaxation of the TSP has an unbounded integrality gap. To do so, we develop a systematic methodology that exploits symmetry. Our methodology allows us to analyze, e.g., SDPs from (some of these SDPs are now known to find equivalent optimal values), and extends to SDP relaxations of the Quadratic Assignment Problem and the k-cycle cover problem. Our results contrast starkly with analysis of the 50-year-old linear program relaxation, whose integrality gap is at most 3/2.In the second part of this thesis, we turn to the prototypical linear program relaxation of the TSP, the subtour elimination LP. We analyze this relaxation on an important but non-metric set of instances: circulant TSP instances. Circulant TSP instances are particularly compelling because circulant instances impose enough structure to make some-but not all-NP-hard problems easy. De Klerk and Dobre (2011) conjectured that, when instances are circulant, the subtour elimination LP is equivalent to a combinatorial lower bound of Van der Veen, Van Dal, and Sierksma (1991). We resolve this conjecture in the affirmative, exploiting symmetry to find a readily-computable, analytic solution to the subtour elimination LP on circulant instances. Using this same symmetry, we show that the integrality gap of the subtour elimination LP on circulant instances is exactly 2; we show that this gap remains unchanged even when the crown, ladder, and chain inequalities are added.
ISBN: 9798641312880Subjects--Topical Terms:
547123
Operations research.
Subjects--Index Terms:
Approximation algorithm
Fantastic Relaxations of the TSP and How to Bound Them: Relaxations of the Traveling Salesman Problem and Their Integrality Gaps.
LDR
:04275nmm a2200385 4500
001
2270169
005
20200921070642.5
008
220629s2020 ||||||||||||||||| ||eng d
020
$a
9798641312880
035
$a
(MiAaPQ)AAI27993667
035
$a
AAI27993667
040
$a
MiAaPQ
$c
MiAaPQ
100
1
$a
Gutekunst, Samuel Christian.
$3
3547538
245
1 0
$a
Fantastic Relaxations of the TSP and How to Bound Them: Relaxations of the Traveling Salesman Problem and Their Integrality Gaps.
260
1
$a
Ann Arbor :
$b
ProQuest Dissertations & Theses,
$c
2020
300
$a
170 p.
500
$a
Source: Dissertations Abstracts International, Volume: 81-12, Section: B.
500
$a
Advisor: Williamson, David P.
502
$a
Thesis (Ph.D.)--Cornell University, 2020.
506
$a
This item must not be sold to any third party vendors.
520
$a
The Traveling Salesman Problem (TSP) is a fundamental problem in combinatorial optimization, combinatorics, and theoretical computer science and is a canonical NP-hard problem. Given a set of n vertices and pairwise costs cij of traveling between vertices i and j, the TSP asks for a minimum-cost tour visiting each of the vertices exactly once (i.e., a minimum-cost Hamiltonian cycle). Despite the problem's ubiquity, the state-of-the-art TSP approximation algorithm dates back more than 40 years. Its performance guarantee can be derived using a linear program relaxation that is over 50 years old, but the best-known analysis of this linear program's integrality gap (which dictates its use in proving approximation guarantees) has not been improved in nearly 40 years of active research. This thesis contributes to two main avenues of TSP research towards breaking these bottlenecks, both of which involve analyzing TSP relaxations.We first consider relaxations of the TSP that are based on semidefinite programs (SDPs). Recently, many such relaxations have been proposed as avenues towards better approximation algorithms. These SDPs exploit a breadth of mathematical structures and have shown considerable promise in small numerical experiments, but little has been known about their general performance. Our first main results fill this void: we provide the first theoretical analysis of the integrality gap of every major SDP relaxation of the TSP. Specifically, with standard costs that are symmetric and obey the triangle inequality, we show that every major SDP relaxation of the TSP has an unbounded integrality gap. To do so, we develop a systematic methodology that exploits symmetry. Our methodology allows us to analyze, e.g., SDPs from (some of these SDPs are now known to find equivalent optimal values), and extends to SDP relaxations of the Quadratic Assignment Problem and the k-cycle cover problem. Our results contrast starkly with analysis of the 50-year-old linear program relaxation, whose integrality gap is at most 3/2.In the second part of this thesis, we turn to the prototypical linear program relaxation of the TSP, the subtour elimination LP. We analyze this relaxation on an important but non-metric set of instances: circulant TSP instances. Circulant TSP instances are particularly compelling because circulant instances impose enough structure to make some-but not all-NP-hard problems easy. De Klerk and Dobre (2011) conjectured that, when instances are circulant, the subtour elimination LP is equivalent to a combinatorial lower bound of Van der Veen, Van Dal, and Sierksma (1991). We resolve this conjecture in the affirmative, exploiting symmetry to find a readily-computable, analytic solution to the subtour elimination LP on circulant instances. Using this same symmetry, we show that the integrality gap of the subtour elimination LP on circulant instances is exactly 2; we show that this gap remains unchanged even when the crown, ladder, and chain inequalities are added.
590
$a
School code: 0058.
650
4
$a
Operations research.
$3
547123
650
4
$a
Applied mathematics.
$3
2122814
650
4
$a
Computer science.
$3
523869
653
$a
Approximation algorithm
653
$a
Circulant
653
$a
Integrality gap
653
$a
Relaxation
653
$a
Semidefinite program
653
$a
Traveling salesman problem
690
$a
0796
690
$a
0364
690
$a
0984
710
2
$a
Cornell University.
$b
Operations Research and Information Engineering.
$3
3169951
773
0
$t
Dissertations Abstracts International
$g
81-12B.
790
$a
0058
791
$a
Ph.D.
792
$a
2020
793
$a
English
856
4 0
$u
http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=27993667
筆 0 讀者評論
館藏地:
全部
電子資源
出版年:
卷號:
館藏
1 筆 • 頁數 1 •
1
條碼號
典藏地名稱
館藏流通類別
資料類型
索書號
使用類型
借閱狀態
預約狀態
備註欄
附件
W9422403
電子資源
11.線上閱覽_V
電子書
EB
一般使用(Normal)
在架
0
1 筆 • 頁數 1 •
1
多媒體
評論
新增評論
分享你的心得
Export
取書館
處理中
...
變更密碼
登入