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

Тип публікації :
Стаття
Дата випуску :
14 січня 2025 р.
Автор(и) :
Скибицький, Н. М.
Денисов, К. І.
Мова основного тексту :
Ukrainian
eKNUTSHIR URL :
DOI :
Журнал :
Випуск :
2
ISSN :
2706-9680
Початкова сторінка :
62
Кінцева сторінка :
67
Цитування :
[APA 7] Скибицький, Н. М., & Денисов, К. І. (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, +) згортки. Журнал обчислювальної та прикладної математики. 2025. № 2. С. 62—67. DOI: 10.17721/2706-9699.2024.2.04 (дата звернення: 25.07.2026).
У статтi дослiджено одновимiрний варiант задачi комiвояжера з квотою та її зв’язок iз задачею про (min, +) згортку. Запропоновано ефективнi способи звести цi задачi одна до одної. Отримано умовну нижню оцiнку на обчислювальну складнiсть варiанта задачi комiвояжера з квотою. Окремо видiлено практичне значення опуклостi в обох задачах та її зв’язок iз запропонованими способами зведення.
Ключові слова :
traveling salesman problem min-plus-convolution computational complexity fine-grained reduction задача комiвояжера min-плюс-згортка обчислювальна складнiсть обчислювально ефективнi зведення
Галузі знань та спеціальності :
11 Математика та статистика
Галузі науки і техніки (FOS) :
Природничі науки
Файл(и) :
Вантажиться...
Ескіз
Завантажити
Формат :

Adobe PDF

Розмір :

557.8 KB

Контрольна сума :

(MD5):33cdb0c0c3c4c4feeb067a6736fa7886

Creative Commons Attribution 4.0 International
Якщо не вказано інше, ця робота розповсюджується на умовах ліцензії Creative Commons Attribution 4.0 International