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

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.