Том 5, серия 1, номер 4, 1998 г., Стр. 45-60
УДК 519.8
В. П. Ильев
Оценка точности алгоритма жадного спуска для задачи минимизации супермодулярной функции
Аннотация:
Рассматривается задача минимизации невозрастающей супермодулярной функции, частным случаем которой является задача о $р$-медиане на минимум. Как и задача о $р$-медиане, рассматриваемая задача является NP-трудной. Для приближенного решения этой задачи рассматривается вариант жадного алгоритма, являющийся дискретным аналогом алгоритма наискорейшего спуска. В терминах некоторых характеристик целевой функции и параметров допустимой области получена достижимая гарантированная оценка погрешности этого алгоритма.
Ильев В. П. 1
1. Омский государственный университет,
а/я 8501, 644070 Омск, Россия
е-mail: iljev@iitam.omsk.net.ru
Статья поступила 11 февраля 1998 г.
