Том 15, номер 1, 2008 г., Стр. 44-57
УДК 519.8
В. П. Ильев
Оценки погрешности жадных алгоритмов для задач на наследственных системах
Аннотация:
Исследуются задачи максимизации и минимизации аддитивных функций на наследственных системах, которые являются обобщениями многих сложных в вычислительном отношении задач комбинаторной оптимизации. Доказана оценка погрешности жадного алгоритма в терминах параметров допустимой области и целевой функции задачи максимизации, обобщающая и уточняющая известную оценку Дженкинса–Корте–Хаусмана. Аналогичный результат получен для задачи минимизации аддитивной функции на наследственной системе.
Библ. 6.
В. П. Ильев 1
1. Омский государственный университет,
пр. Мира, 55а, 644077 Омск, Россия
е-mail: iljev@math.omsu.omskreg.ru
Статья поступила 30 октября 2007 г.
