EN|RU

Том 4, серия 1, номер 3, 1997 г., Стр. 35-48

УДК 519.8
М. И. Свириденко
О точности решений жадными алгоритмами задач размещения на максимум

Аннотация:
В [2, 3, 7] предложены жадные алгоритмы для решения с гарантированными оценками погрешностей следующих задач размещения: задачи о $р$-медиане на максимум и взвешенной задачи о $р$-медиане на максимум. При получении априорных оценок погрешностей существенно использовалась субмодулярность целевой функции. В настоящей работе рассматриваются задачи с дополнительными ресурсными ограничениями. Устанавливается свойство задач, позволяющее найти априорные оценки точности решений. Погрешность решений зависит от числа добавляемых ограничений, и если их число равно нулю, оценки совпадают с уже полученными в [2, 3, 7].
Библиогр. 7.

Свириденко М. И. 1
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия

Статья поступила 18 марта 1996 г.
Исправленный вариант — 23 апреля 1997 г.

 © Институт математики им. С. Л. Соболева, 2015