Analysis of Detour Gap Numbers Open Access
Lou, Siyuan (2012)
Abstract
Spanner graphs appear in approximation schemes for problems such as the Traveling Salesman Problem, where an edge weighted graph defines a metric on its vertex set. In such schemes, a spanner is a subgraph of the input graph, which still represents nearly the same metric. We bound its total edge weight using the "detour gap number", which is defined by a linear program. In this thesis, we simplify this linear program, and state the complementary slackness conditions relating it and its dual. We also give a way to prune a graph based on those properties and a counter example showing the detour gap number is not monotone under edge deletion. The thesis also introduced a software package to facilitate the calculation of detour gap numbers.
Table of Contents
Content
1 Introduction
2 The Primal Problem
2.1 Simplification
2.2 RunningExample
3 Dual Problem
3.1 ChargingScheme
3.2 RunningExample
4 Combined Primal and Dual
4.1 ComplementarySlackness
4.2 RunningExample
5 Graph Modification
5.1 TreeEdgeContraction
5.2 ParallelEdgeDeletion
6 Nonmonotonicity in Edge Deletion
7 Software
About this Master's Thesis
School | |
---|---|
Department | |
Degree | |
Submission | |
Language |
|
Research Field | |
Keyword | |
Committee Chair / Thesis Advisor | |
Committee Members |
Primary PDF
Thumbnail | Title | Date Uploaded | Actions |
---|---|---|---|
Analysis of Detour Gap Numbers () | 2018-08-28 11:04:36 -0400 |
|
Supplemental Files
Thumbnail | Title | Date Uploaded | Actions |
---|---|---|---|
Gap.zip () | 2018-08-28 11:07:54 -0400 |
|