Вариант 794034882.
Задача Коммивояжера, в которой для матрицы расстояний выполнено неравенство треугольника, называется:
Есть граф G=(V,E). Разбиение множества вершин V на непересекающиеся множества S и T называется:
Для чего применяется «дерандомизация»:
В теме о полиномиальном в среднем алгоритме для задачи о рюкзаке рассматривался алгоритм, который оперирует множеством…
Как называется задача оптимизации со следующей формулировкой:
Какой алгоритм используется в алгоритме Кристофидеса?
Какой алгоритм используется в рассмотренных FPTAS-алгоритмах для рюкзака?
С какой точностью работает модифицированный жадный алгоритм для задачи о рюкзаке из соответствующей темы?
Цикл, проходящий через все ребра графа по одному разу, называется