COMPUTATIONAL EQUIVALENCE OF ONE-DIMENSIONAL QUOTA TSP VARIANT AND (MIN, +) CONVOLUTION
Abstract
The paper considers a variant of the one-dimensional quota traveling salesman problem and its connection to the (min, +) convolution problem. We propose fine-grained reductions between these problems, resulting in a conditional lower bound on the computational complexity of the quota traveling salesman problem variant. We highlight the role of convexity in both problems and its connection to the proposed reductions.
References
Williams V. On some fine-grained questions in algorithms and complexity. Proceedings of the ICM. 2018. P. 3447–3487.
Williams V. Some Open Problems in Fine-Grained Complexity. SIGACT News. 2018. Vol. 49, No. 4. P. 29–35.
Bremner D. et al. Necklaces, Convolutions, and X+Y. Algorithmica. 2012. Vol. 69.
Cygan M., Mucha M., Wegrzycki K., Wlodarczyk M.. On Problems Equivalent to (min,+)-Convolution. ACM Trans. Algorithms. 2019. Vol. 15, No. 1.
de Berg M., Buchin K., Jansen B., Woeginger G. Fine-grained Complexity Analysis of Two Classic TSP Variants. ACM Trans. Algorithms. 2021. Vol. 17, No. 1.
Bringmann K., Cassis A. Faster Knapsack Algorithms via Bounded Monotone Min-Plus-Convolution. arXiv:1212.4771. 2022.
Eppstein D., Galil Z., Giancarlo R. Speeding up dynamic programming. In Proceedings of the 29th Annual SFCS. 1988. P. 488–496.
Bringmann K., Cassis A. Faster 0-1-Knapsack via Near-Convex Min-Plus-Convolution. arXiv:2305.01593. 2023.
