Оптимизация и распараллеливание упрощенного алгоритма Балаша–Кристофидеса для задачи коммивояжера

В работе описывается точный параллельный алгоритм для задачи коммивояжера, основанный на упрощенном алгоритме Балаша–Кристофидеса, его оптимизация и увеличение эффективности распараллеливания. За счет нового метода передачи заданий между параллельными потоками алгоритм способен решать задачи с 3000 вершинами (со случайными весами дуг), в среднем, за минуту, а задачи с 10000 вершинами — за 50 минут. Возможность решать задачи с более чем 3000 вершинами появилась благодаря проведенной автором оптимизации расхода памяти.