Том 7, серия 1, номер 1, 2000 г., Стр. 6-17

УДК 519.95
М. Ю. Мошков
О работах Р. Г. Нигматуллина по приближённым алгоритмам решения дискретных экстремальных задач

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

Мошков М. Ю. ¹
1. НИИ прикладной математики и кибернетики ННГУ,
ул. Ульянова, 10, 603005 Нижний Новгород, Россия
е-mail: moshkov@nnucnit.unn.ac.ru

Статья поступила 10 ноября 1999 г.