Abstract: Для задач дискретной оптимизации основным фактором, определяющим реализуемость алгоритмов их решения, является размерность (длина записи входа) задачи, которая в 50-70 г.г. прошлого века ассоциировалась с понятием “проклятия размерности” (curse of dimensionality). В противовес понятию "проклятия размерности" в рамках асимптотически точного (asymptotically optimal) подхода к (приближенному) решению трудных задач дискретной оптимизации размерность задачи является нашим другом и союзником. К настоящему моменту определилось немало примеров реализации подхода к решению некоторых большеразмерных (large scale) задач дискретной оптимизации в исследованиии операций, в которых докладчик за последние пол-века принимал непосредственное участие.\\ Речь идет о таких задачах, как задачи маршрутизации, многоиндексные задачи о назначениях, задачи кластеризации, задачи размещения, экстремальные задачи на графах и сетях и т.п.

Cite: Гимади Э.Х.
Асимптотически точный подход к решению трудных задач дискретной оптимизации vs проклятие размерности. с. 51
International Conference "Mathematics in the Modern World" dedicated to the 60th anniversary of the foundation of the Sobolev Institute of Mathematics 14-19 авг. 2017