Еквiвалентнiсть обчислювальної складностi одновимiрного варiантазадачi комiвояжера з квотою та (min, +) згортки

Скибицький, Н. М., Денисов, К. I. (2025). Еквiвалентнiсть обчислювальної складностi одновимiрного варiантазадачi комiвояжера з квотою та (min, +) згортки. Журнал обчислювальної та прикладної математики, 2, 62–67. https://doi.org/10.17721/2706-9699.2024.2.04

У статтi дослiджено одновимiрний варiант задачi комiвояжера з квотою та її зв’язок iз задачею про (min, +) згортку. Запропоновано ефективнi способи звести цi задачi одна до одної. Отримано умовну нижню оцiнку на обчислювальну складнiсть варiанта задачi комiвояжера з квотою. Окремо видiлено практичне значення опуклостi в обох задачах та її зв’язок iз запропонованими способами зведення.