Ukrainian
Summary:У монографії запропоновано теоретичний фундамент для отримання, дослідження та використання оцінок складності постоптимального аналізу, здійснено подальший розвиток і удосконалення наближених алгоритмів реоптимізації розв’язування задач дискретної оптимізації. Зокрема, отримано верхні та нижні оцінки відношення апроксимації наближених алгоритмів реоптимізації з використанням напіввизначеної та лінійної релаксацій початкових задач. Отримано достатні умови існування поліноміальних наближених оптимальних або порогових алгоритмів реоптимізації для узагальнених задач про виконуваність. Запропоновано підхід до проектування поліноміальних (порогових) алгоритмів реоптимізації для задач дискретного програмування, який має місце і для сублінійних алгоритмів константної складності.
Reading audience:Для широкого кола наукових співробітників, аспірантів та студентів, які цікавляться наближеними методами розв’язування задач дискретного програмування.
Russian
Summary:В монографии предложен теоретический фундамент для получения, исследования и использования оценок сложности постоптимального анализа, осуществлено дальнейшее развитие и совершенствование приближенных алгоритмов реоптимизации решения задач дискретной оптимизации. В частности, получены верхние и нижние оценки отношения аппроксимации приближенных алгоритмов реоптимизации с использованием полуопределенной и линейной релаксационных начальных задач. Получены достаточные условия существования полиномиальных приближенных оптимальных или пороговых алгоритмов реоптимизации для обобщенных задач о выполнимости. Предложен подход к проектированию полиномиальных (пороговых) алгоритмов реоптимизации для задач дискретного программирования, который имеет место и для сублинейных алгоритмов константной сложности.
Reading audience:Для широкого круга научных сотрудников, аспирантов и студентов, интересующихся приближенными методами решения задач дискретного программирования.