Summary |
For almost all computational problems on point sets, the complexity increases as the dimension increases. In this project we investigate what happens when the points in the input set “almost” lie in a lower-dimensional subspace. As a concrete example, consider the famous Traveling Salesman Problem (TSP). TSP is trivial in 1-dimensional space, and NP-hard in the plane. Now suppose the input point set is drawn uniformly at random from a δ x n rectangle. For which values of δ can we still solve TSP in polynomial time? And can we develop an algorithm that is FPT in δ? |