Скибицький, Н. М.Н. М.СкибицькийДенисов, К. І.К. І.Денисов2026-02-262026-02-262025-01-14Скибицький, Н. М., Денисов, К. I. (2025). Еквiвалентнiсть обчислювальної складностi одновимiрного варiантазадачi комiвояжера з квотою та (min, +) згортки. Журнал обчислювальної та прикладної математики, 2, 62–67. https://doi.org/10.17721/2706-9699.2024.2.04УДК 519.1,519.710.17721/2706-9699.2024.2.04https://ir.library.knu.ua/handle/15071834/10871The 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.У статтi дослiджено одновимiрний варiант задачi комiвояжера з квотою та її зв’язок iз задачею про (min, +) згортку. Запропоновано ефективнi способи звести цi задачi одна до одної. Отримано умовну нижню оцiнку на обчислювальну складнiсть варiанта задачi комiвояжера з квотою. Окремо видiлено практичне значення опуклостi в обох задачах та її зв’язок iз запропонованими способами зведення.uktraveling salesman problemmin-plus-convolutioncomputational complexityfine-grained reductionзадача комiвояжераmin-плюс-згорткаобчислювальна складнiстьобчислювально ефективнi зведенняСтаття