Задача 1-центра , также известная как задача минимакса или задача минимаксного размещения , является классической задачей комбинаторной оптимизации в исследовании операций типа размещения объектов . В самом общем случае задача формулируется следующим образом: задан набор из n точек спроса, пространство возможных местоположений объекта и функция для расчета стоимости транспортировки между объектом и любой точкой спроса, найти местоположение объекта, которое минимизирует максимальную стоимость транспортировки объекта-точки спроса.
Существует множество частных случаев этой задачи, зависящих от выбора местоположений как точек спроса, так и объектов, а также функции расстояния.
Простой частный случай — когда возможные местоположения и точки спроса находятся на плоскости с евклидовым расстоянием в качестве транспортных расходов ( плоская задача minmax евклидовой задачи размещения объектов, евклидова задача с 1 центром на плоскости и т. д.). Она также известна как задача о наименьшем круге . Ее обобщение на n -мерные евклидовы пространства известно как задача о наименьшем объемлющем шаре . Дальнейшее обобщение ( взвешенное евклидово местоположение объектов ) — когда набор весов назначается точкам спроса, а транспортные расходы представляют собой сумму произведений расстояний на соответствующие веса. Другой частный случай — задача о ближайшей строке — возникает, когда входные данные представляют собой строки , а их расстояние измеряется с помощью расстояния Хэмминга .
Проблему 1-центра можно переформулировать как нахождение звезды во взвешенном полном графе , которая минимизирует максимальный вес выбранных ребер. Соответствующая задача минимизации максимального веса пути между двумя выбранными вершинами вместо звезды называется задачей минимаксного пути .