Abstract: Исследована задача размещения объектов с максиминным критерием на геометрической сети, расположенной на плоскости с ограничениями на минимально допустимые расстояния между вершинами и объектами и объектов между собой. Для решения задачи с одним объектом предложены точные полиномиальные алгоритмы с применением диаграммы Вороного и условий Каруша-Куна-Таккера. Для двух объектов разработан полиномиальный алгоритм поиска приближенного решения с заданной точностью с помощью построения выпуклой оболочки конечного множества допустимых точек и поиска ее диаметра. Приведена трудоемкость предложенных алгоритмов.

Cite: Забудский г.г.
Решение максиминной задачи размещения с минимальными расстояниями на сети
Научная конференция сотрудников ИМ СО РАН, посвященная подведению итогов 2025 года 27-28 нояб. 2025