• FAQ
    • Deposit your work
    • Login
    View Item 
    •   Rice Scholarship Home
    • Rice University Graduate Electronic Theses and Dissertations
    • Rice University Electronic Theses and Dissertations
    • View Item
    •   Rice Scholarship Home
    • Rice University Graduate Electronic Theses and Dissertations
    • Rice University Electronic Theses and Dissertations
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    On the Integrality Gap of the Subtour Relaxation of the Traveling Salesman Problem for Certain Fractional 2-matching Costs

    Thumbnail
    Name:
    FAST-THESIS-2014.pdf
    Size:
    556.8Kb
    Format:
    PDF
    View/Open
    Author
    Fast, Caleb
    Date
    2014-04-11
    Advisor
    Hicks, Illya V.
    Degree
    Master of Arts
    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.
    Keyword
    Traveling salesman problem (TSP); Fractional 2-matching instance; Subtour elimination; 4/3 conjecture; Integrality gap; More... Applied mathematics Less...
    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. http://hdl.handle.net/1911/76721.
    Metadata
    Show full item record
    Collections
    • Rice University Electronic Theses and Dissertations [10740]

    Home | FAQ | Contact Us
    Managed by the Digital Scholarship Services at Fondren Library, Rice University
    Physical Address: 6100 Main Street, Houston, Texas 77005
    Mailing Address: MS-44, P.O.BOX 1892, Houston, Texas 77251-1892
     

     

    Browse

    Entire ArchiveCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsTypeThis CollectionBy Issue DateAuthorsTitlesSubjectsType

    My Account

    Login

    Statistics

    View Usage Statistics

    Home | FAQ | Contact Us
    Managed by the Digital Scholarship Services at Fondren Library, Rice University
    Physical Address: 6100 Main Street, Houston, Texas 77005
    Mailing Address: MS-44, P.O.BOX 1892, Houston, Texas 77251-1892