ЕКВIВАЛЕНТНIСТЬ ОБЧИСЛЮВАЛЬНОЇ СКЛАДНОСТI ОДНОВИМIРНОГО ВАРIАНТА ЗАДАЧI КОМIВОЯЖЕРА З КВОТОЮ ТА (MIN, +) ЗГОРТКИ
DOI:
https://doi.org/10.17721/2706-9699.2024.2.04Ключові слова:
задача комiвояжера, min-плюс-згортка, обчислювальна складнiсть, обчислювально ефективнi зведенняАнотація
У статтi дослiджено одновимiрний варiант задачi комiвояжера з квотою та її зв’язок iз задачею про (min, +) згортку. Запропоновано ефективнi способи звести цi задачi одна до одної. Отримано умовну нижню оцiнку на обчислювальну складнiсть варiанта задачi комiвояжера з квотою. Окремо видiлено практичне значення опуклостi в обох задачах та її зв’язок iз запропонованими способами зведення.
Посилання
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.
