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.
