Analysis of Detour Gap Numbers Pubblico

Lou, Siyuan (2012)

Permanent URL: https://etd.library.emory.edu/concern/etds/9s161628x?locale=it
Published

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

Rights statement
  • Permission granted by the author to include this thesis or dissertation in this repository. All rights reserved by the author. Please contact the author for information regarding the reproduction and use of this thesis or dissertation.
School
Department
Degree
Submission
Language
  • English
Research Field
Parola chiave
Committee Chair / Thesis Advisor
Committee Members
Ultima modifica

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