Title page for ETD etd-0823102-142941


Type of Document Master's Thesis
Author Augustine, John Ebenezer
URN etd-0823102-142941
Title Offline and Online Variants of the Traveling Salesman Problem
Degree Master of Science in Electrical Engineering (M.S.E.E.)
Department Electrical and Computer Engineering
Advisory Committee
Advisor Name Title
Jaganathan Ramanujam Committee Co-Chair
Steven Seiden Committee Co-Chair
Jerry Trahan Committee Member
R. Vaidyanathan Committee Member
Keywords
  • algorithms
  • online
  • vehicle scheduling
Date of Defense 2002-06-21
Availability unrestricted
Abstract
In this thesis, we study several well-motivated variants of the Traveling Salesman Problem (TSP). First, we consider makespan minimization for vehicle scheduling problems on trees with release and handling times. 2-approximation algorithms were known for several variants of the single vehicle problem on a path. A 3/2-approximation algorithm was known for the single vehicle problem on a path where there is a fixed starting point and the vehicle must return to the starting point upon completion. Karuno, Nagamochi and Ibaraki give a 2-approximation algorithm for the single vehicle problem on trees. We develop a Polynomial Time Approximation Scheme (PTAS) for the single vehicle scheduling problem on trees which have a constant number of leaves. This PTAS can be easily adapted to accommodate various starting/ending constraints. We then extended this to a PTAS for the multiple vehicle problem where vehicles operate in disjoint subtrees. We also present competitive online algorithms for some single vehicle scheduling problems.

Secondly, we study a class of problems called the Online Packet TSP Class (OP-TSP-CLASS). It is based on the online TSP with a packet of requests known and available for scheduling at any given time. We provide a 5/3 lower bound on any online algorithm for problems in OP-TSP-CLASS. We extend this result to the related k-reordering problem for which a 3/2 lower bound was known. We develop a κ+1-competitive algorithm for problems in OP-TSP-CLASS, where a κ-approximation algorithm is known for the offline version of that problem. We use this result to develop an offline m(κ+1)-approximation algorithm for the Precedence-Constrained TSP (PCTSP) by segmenting the n requests into m packets. Its running time is mf(n/m) given a κ-approximation algorithm for the offline version whose running time is f(n).

Files
  Filename       Size       Approximate Download Time (Hours:Minutes:Seconds) 
 
 28.8 Modem   56K Modem   ISDN (64 Kb)   ISDN (128 Kb)   Higher-speed Access 
  Augustine_thesis.pdf 609.09 Kb 00:02:49 00:01:27 00:01:16 00:00:38 00:00:03

Browse All Available ETDs by ( Author | Department )

If you have questions or technical problems, please Contact LSU-ETD Support.