@inproceedings{
min2023unsupervised,
title={Unsupervised Learning Permutations for {TSP} using Gumbel-Sinkhorn Operator},
author={Yimeng Min and Carla Gomes},
booktitle={NeurIPS 2023 Workshop Optimal Transport and Machine Learning},
year={2023},
url={https://openreview.net/forum?id=9xW9OgdJfs}
}
The Machine Learning community has recently shown a growing interest in Optimal Transport (OT). Methods that leverage entropy regularization based on OT have proven especially effective for various tasks, including ranking, sorting, and solving jigsaw puzzles. In our study, we broaden the application of entropy regularization methods to address the NP-hard Travelling Salesman Problem (TSP). We first formulate TSP as identifying the permutation of a Hamiltonian Cycle with the shortest length. Following this, we establish the permutation representation using the Gumbel-Sinkhorn operator with entropic regularization. Our findings indicate a balance between entropy and generalization. We further discuss how to generalize across different hardnesses.
Unsupervised Learning Permutations for TSP using Gumbel-Sinkhorn Operator
Yimeng Min Carla Gomes