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

Алгоритм y-аппроксимации представляет собой полиномиальный алгоритм, который в задаче минимизации гарантированно дает допустимое решение со значением, не превышающим у z*, где z* - значение оптимального решения, а у > 1. Если у = 1, алгоритм дает оптимальное решение. В задаче минимизации алгоритм дает решение со значением не менее yz*, где 0 < у < 1.