K. I. Denysov

COMPUTATIONAL EQUIVALENCE OF ONE-DIMENSIONAL QUOTA TSP VARIANT AND (MIN, +) CONVOLUTION

2024 · Journal of Numerical and Applied Mathematics

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 …