Задача о размещении объектов: различия между версиями

В последние годы были проведены масштабные исследования алгоритмов аппроксимации для задач о размещении объектов. Обзорные материалы по этим исследованиям выпустили Шмойс [49, 50] и Вайген [55]. Помимо их теоретической и практической важности, задачи о размещении объектов представляют собой яркую демонстрацию применения широко распространенных техник в области алгоритмов аппроксимации, поскольку многие из этих техник (например, округление LP-алгоритма, прямо-двойственные методы и локальный поиск) успешно применяются к этому семейству задач. Далее будут рассмотрены насколько задач о размещении объектов, выполнен экскурс в историю и перечислены алгоритмы аппроксимации с опорой на результаты, полученные в работе Шмойса, Тардош и Аардал [51]. Техники, применяемые к ''задаче о размещении объектов без ограничений на пропускную способность'' (uncapacitated facility location, UFL), будут рассмотрены более подробно.