О точности решений жадными алгоритмами задач размещения на максимум

Известно, что решения задачи о $p$-медиане на максимум, получаемые жадными алгоритмами, имеют относительную погрешность $1-e^{-1}$ . При построении оценок существенно используется субмодулярность целевой функции. В работе рассматриваются задачи с дополнительными ресурсными ограничениями. Устанавливается свойство задач, позволяющее найти априорные оценки точности решений. Погрешность решений зависит от числа добавляемых ограничений, и, если их число равно нулю, оценки совпадают с уже полученными для задачи о $p$-медиане на максимум.
Библиогр. 7