TOWARDS IMPROVING UPON CHRISTOFIDES APPROXIMATION ALGORITHM FOR TSP
Abstract
Many of the important network optimization problems that arise in practice are known to be NP-hard, i.e., we do not expect to solve them optimally efficiently. One of most well-known of these is the Traveling Salesman Problem (TSP). The metric TSP problem is the following: given a list of n cities, V, and their pairwise symmetric distances, c(u; v) for all u, v in V, assumed to satisfy the triangle inequality, find the shortest tour that visits each city exactly once and returns back to the starting point. The TSP is one of the most fundamental problems in algorithms, network optimization and operations re- search. Since we cannot solve TSP optimally, the best we can hope for is to design approximation algorithms. The best-known approximation algorithm for TSP is a 3/2-approximation designed by Christodes back in 1976, i.e., the algorithm, provably, always returns a solution of cost no more than 50% of the optimum. It is a long-standing open problem to break the 3/2 barrier. Christodes algorithm has been used as a primitive in many real world applications of TSP. In this project, the PIs intend to prove that the maximum entropy rounding algorithm, previously proposed by one of the PIs (and coauthors) a decade ago, beats the 3/2 barrier. The proof is expected to use several new tools in probability theory, polyhedral theory and graph theory,
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Aug 12, 2021
- Source ID
- FA95502010212
Entities
People
- Shayan Gharan
Organizations
- Air Force Office of Scientific Research
- United States Air Force
- University of Washington