Оценки погрешности жадных алгоритмов для задач на наследственных системах

Исследуются задачи максимизации и минимизации аддитивных функций на наследственных системах, которые являются обобщениями многих сложных в вычислительном отношении задач комбинаторной оптимизации. Доказана оценка погрешности жадного алгоритма в терминах параметров допустимой области и целевой функции задачи максимизации, уточняющая известную оценку Дженкинса–Корте–Хаусмана. Аналогичный результат получен для задачи минимизации аддитивной функции на наследственной системе. Библ. 6.