A Modular-Form Framework for Global Optimality in the Asymmetric Traveling-Salesman Problem

Abstract

In this paper, we develop an alternate formulation of Asymmetric Traveling Salesman Problem (ATSP). The equivalent problem is to find the zeros of a holomorphic cusp form on the principal congruence subgroup, $\hat{I}“(4)$. The resultant Poincar{é} series gives a cusp form whose interior zeros are in bijection with the arc that constitute optimal Hamiltonian cycle. We show that for any weight, $\ell$ and number of directed arcs, $|A|$ such that $4\ell -7<2|A|$, the holomorphic cusp form vanishes at global optimum. Furthermore, a three step filter consisting of Fourier coefficients, Hecke recursions and completed $L$-function parity test provides a scalar certificate for global optimality. The framework is a potential bridge between discrete optimization and number theory suggesting an alternate view on complexity theory.