Алгоритм с оценкой точности для дискретной задачи Вебера

Рассматривается релаксация квадратичной задачи о назначениях, в которой ограничение на число размещенных в позицию объектов отсутствует. Такая задача в общем случае является $NP$-трудной. Для решения исследуемой задачи предложен полиномиальный алгоритм с гарантированной апостериорной оценкой точности; выделен класс задач со специальными функциями стоимости размещения, на котором алгоритм является $2$-приближенным. Доказано, что если размещаемый граф содержит один простой цикл, а множество позиций размещения является метрическим пространством, то предложенный алгоритм является $2$-приближенным и гарантированно асимптотически точным. Проведен вычислительный эксперимент по анализу погрешности алгоритма и его оценки точности.

Статья представлена к публикации членом редколлегии: П. Ю. Чеботарев