Show simple item record

dc.contributor.advisor Hicks, Illya V.
dc.creatorFast, Caleb
dc.date.accessioned 2014-08-26T21:08:37Z
dc.date.available 2014-08-26T21:08:37Z
dc.date.created 2014-05
dc.date.issued 2014-04-11
dc.date.submitted May 2014
dc.identifier.citation Fast, Caleb. "On the Integrality Gap of the Subtour Relaxation of the Traveling Salesman Problem for Certain Fractional 2-matching Costs." (2014) Master’s Thesis, Rice University. https://hdl.handle.net/1911/76721.
dc.identifier.urihttps://hdl.handle.net/1911/76721
dc.description.abstract This thesis provides new bounds on the strength of the subtour relaxation of the Traveling Salesman Problem (TSP) for fractional 2-matching cost instances whose support graphs have no fractional cycles larger than five vertices. This work provides insight for improving approximation heuristics for the TSP and into the structure of solutions produced by the subtour relaxation. Guided by a T-join derived from the subtour relaxation, I form a tour by adding edges to the subtour relaxation. By this constructive process, I prove that the optimal solution of the TSP is within 4/3, 17/12, or strictly less than 3/2 of the optimal solution of the subtour relaxation. Thus, this thesis takes a step towards proving the 4/3 conjecture for the TSP and the development of a 4/3 approximation algorithm for the TSP. These developments would provide improved approximations for applications such as DNA sequencing, route planning, and circuit board testing.
dc.format.mimetype application/pdf
dc.language.iso eng
dc.subjectTraveling salesman problem (TSP)
Fractional 2-matching instance
Subtour elimination
4/3 conjecture
Integrality gap
Applied mathematics
dc.title On the Integrality Gap of the Subtour Relaxation of the Traveling Salesman Problem for Certain Fractional 2-matching Costs
dc.contributor.committeeMember Bixby, Robert E.
dc.contributor.committeeMember Cooper, Keith D.
dc.contributor.committeeMember Tapia, Richard A.
dc.date.updated 2014-08-26T21:08:37Z
dc.type.genre Thesis
dc.type.material Text
thesis.degree.department Computational and Applied Mathematics
thesis.degree.discipline Engineering
thesis.degree.grantor Rice University
thesis.degree.level Masters
thesis.degree.name Master of Arts


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record