Research on the k-TSP Problem with Professor Yuefan Deng at Stony Brook University

Our research aimed to find the shortest path between k points when choosing from a larger set of n points, while minimizing the computation time and ensuring that the time scales linearly with the number of points. We implemented a fixed approximation algorithm in C on the Stony Brook supercomputers and compared its performance to a previously implemented brute force method.

Problem Statement

The k-TSP problem involves finding the shortest path that passes through k points in a set of n points. This problem is known to be NP-hard, making it computationally expensive to solve. The goal of our research was to develop an algorithm that could efficiently and accurately solve the problem.

Algorithm Design

We designed a fixed approximation algorithm that produces the same results as the brute force method but with much less computation time. Our algorithm involves starting with a subset of the n points and iteratively adding more points to the subset until we have k points. We then use a heuristic to find the shortest path that passes through the k points in the subset. We repeat this process multiple times with different subsets of points, each time starting with a larger subset, until we obtain the optimal solution.

We also improved our original algorithm by reducing the frequency of restarts after the approximation algorithm with double the length, which further reduced the computation time while ensuring the same level of accuracy.

Results

We verified the accuracy of our algorithm by comparing its results with the brute force method. Our algorithm produced the same results as the brute force method, but with significantly less computation time. The time required to solve the problem scaled linearly with the number of points, as we had hoped.