2014 Rice Oil & Gas HPC has ended
Back To Schedule
Thursday, March 6 • 4:30pm - 6:30pm
Poster: Approximating Traveling Salesman and p-Median Solutions using Linear Relaxations, Caleb Fast, Rice University

Sign up or log in to save this to your schedule, view media, leave feedback and see who's attending!

This poster presents a method for developing improved approximation algorithms for two common problems from operations research, the traveling salesman problem (TSP) and the p-median problem (PMP). The PMP and the TSP are of interest because of their exceptionally wide applicability. The TSP is used for many problems, such as planning routes for geological survey or collection vehicles, as well as other problems, such as DNA sequencing. The PMP meanwhile is used for facility location problems, such as determining locations for fuel stations. These problems are commonly attacked using the linear relaxation of an integer programming formulation. However, in neither problem is the error bound of the relaxation well-known. This poster presents a method both for understanding the errors of the relaxations, and for finding approximate integral solutions to the problems when the linear solution is half-integral. The approximate solutions found are better than current state-of-the-art algorithms. For each problem, the method is based on solving a different, ideally tractable problem, and then using the solution of the simpler problem to compute a solution of the original. In the case of the TSP, I solve a matching problem on the support graph of the linear relaxation, while in the case of the PMP, I solve a dominating set problem. The solutions of these problems show which fractional edges of the support graph should be included in the optimal solution and which should be removed.


Thursday March 6, 2014 4:30pm - 6:30pm PST
BRC Exhibit Hall Rice University 6500 Main Street at University, Houston, TX 77030

Attendees (0)