О работах Р. Г. Нигматуллина по приближенным алгоритмам решения дискретных экстремальных задач

Работы Р. Г. Нигматуллина оказали заметное влияние на развитие исследований приближенных алгоритмов решения дискретных экстремальных задач. Он получил оценки мультипликативной точности жадного алгоритма решения задачи о покрытии и доказал, что многие сложные задачи сводятся к своим приближенным с некоторой аддитивной точностью. В статье рассматриваются четыре работы Р. Г. Нигматуллина, посвященные изучению приближенных алгоритмов, приводятся некоторые результаты последних лет, относящиеся к исследованиям мультипликативной точности жадного алгоритма и мультипликативной точности приближенных полиномиальных алгоритмов решения задачи о раскраске графа и задачи о покрытии, а также обсуждается близкая к задаче о покрытии задача построения минимального по глубине дерева решений. Библиогр. 28.