A Modular-Form Framework for Global Optimality in the Asymmetric Traveling-Salesman Problem
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866911269175427072 |
|---|---|
| author | Gupta, Varsha |
| author_facet | Gupta, Varsha |
| contents | 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, $Γ(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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_15546 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A Modular-Form Framework for Global Optimality in the Asymmetric Traveling-Salesman Problem Gupta, Varsha Combinatorics Optimization and Control 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, $Γ(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. |
| title | A Modular-Form Framework for Global Optimality in the Asymmetric Traveling-Salesman Problem |
| topic | Combinatorics Optimization and Control |
| url | https://arxiv.org/abs/2404.15546 |