Travel the Same Path: A Novel TSP Solving Strategy

Author name not available (Why is that?)

Publication date: 11 October 2022

Abstract: In this paper, we provide a novel strategy for solving Traveling Salesman Problem, which is a famous combinatorial optimization problem studied intensely in the TCS community. In particular, we consider the imitation learning framework, which helps a deterministic algorithm making good choices whenever it needs to, resulting in a speed up while maintaining the exactness of the solution without suffering from the unpredictability and a potential large deviation. Furthermore, we demonstrate a strong generalization ability of a graph neural network trained under the imitation learning framework. Specifically, the model is capable of solving a large instance of TSP faster than the baseline while has only seen small TSP instances when training.

Has companion code repository: https://github.com/sleepymalc/Travel-the-Same-Path

This page was built for publication: Travel the Same Path: A Novel TSP Solving Strategy

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6413646)