Том 4, серия 1, номер 3, 1997 г., Стр. 35-48
УДК 519.8
М. И. Свириденко
О точности решений жадными алгоритмами задач размещения на максимум
Аннотация:
В [2, 3, 7] предложены жадные алгоритмы для решения с гарантированными оценками погрешностей следующих задач размещения: задачи о $р$-медиане на максимум и взвешенной задачи о $р$-медиане на максимум. При получении априорных оценок погрешностей существенно использовалась субмодулярность целевой функции. В настоящей работе рассматриваются задачи с дополнительными ресурсными ограничениями. Устанавливается свойство задач, позволяющее найти априорные оценки точности решений. Погрешность решений зависит от числа добавляемых ограничений, и если их число равно нулю, оценки совпадают с уже полученными в [2, 3, 7].
Библиогр. 7.
Свириденко М. И. 1
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
Статья поступила 18 марта 1996 г.
Исправленный вариант — 23 апреля 1997 г.
|