Traveling salesman path problems
Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 2005.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2006
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/33668 |
| _version_ | 1826212638965628928 |
|---|---|
| author | Lam, Fumei |
| author2 | Michael X. Goemans. |
| author_facet | Michael X. Goemans. Lam, Fumei |
| author_sort | Lam, Fumei |
| collection | MIT |
| description | Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 2005. |
| first_indexed | 2024-09-23T15:30:19Z |
| format | Thesis |
| id | mit-1721.1/33668 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T15:30:19Z |
| publishDate | 2006 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/336682019-04-10T22:31:04Z Traveling salesman path problems Lam, Fumei Michael X. Goemans. Massachusetts Institute of Technology. Dept. of Mathematics. Massachusetts Institute of Technology. Dept. of Mathematics. Mathematics. Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 2005. Includes bibliographical references (p. 153-155). In the Traveling Salesman Path Problem, we are given a set of cities, traveling costs between city pairs and fixed source and destination cities. The objective is to find a minimum cost path from the source to destination visiting all cities exactly once. The problem is a generalization of the Traveling Salesman Problem with many important applications. In this thesis, we study polyhedral and combinatorial properties of a variant we call the Traveling Salesman Walk Problem, in which the minimum cost walk from the source to destination visits all cities at least once. Using the approach of linear programming, we study properties of the polyhedron corresponding to a linear programming relaxation of the traveling salesman walk problem. Our results relate the structure of the underlying graph of the problem instance with polyhedral properties of the corresponding fractional walk polyhedron. We first characterize traveling salesman walk perfect graphs, graphs for which the convex hull of incidence vectors of traveling salesman walks can be described by linear inequalities. We show these graphs have a description by way of forbidden minors and also characterize them constructively. (cont.) We extend these results to relate the underlying graph structure to the integrality gap of the corresponding fractional walk polyhedron. We present several graph operations which preserve integrality gap; these operations allow us to find the integrality gap of graphs built from smaller bricks, whose integrality gaps can be found by computational or other methods. by Fumei Lam. Ph.D. 2006-07-31T15:21:53Z 2006-07-31T15:21:53Z 2005 2005 Thesis http://hdl.handle.net/1721.1/33668 64564874 eng M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission. http://dspace.mit.edu/handle/1721.1/7582 155 p. 9104947 bytes 9111456 bytes application/pdf application/pdf application/pdf Massachusetts Institute of Technology |
| spellingShingle | Mathematics. Lam, Fumei Traveling salesman path problems |
| title | Traveling salesman path problems |
| title_full | Traveling salesman path problems |
| title_fullStr | Traveling salesman path problems |
| title_full_unstemmed | Traveling salesman path problems |
| title_short | Traveling salesman path problems |
| title_sort | traveling salesman path problems |
| topic | Mathematics. |
| url | http://hdl.handle.net/1721.1/33668 |
| work_keys_str_mv | AT lamfumei travelingsalesmanpathproblems |