Метод эллипсоидов, предложенный советским математиком Леонидом Хачияном в 1979 году, стал исторической вехой в математическом программировании. Этот алгоритм впервые строго доказал, что задачи линейного программирования могут быть решены за полиномиальное время. В отличие от классического симплекс-метода, который в худших сценариях (например, на кубе Клее-Минти) требует экспоненциального количества шагов, метод эллипсоидов гарантирует нахождение оптимума с оценкой сложности, зависящей только от размера входных данных, что навсегда изменило теоретический ландшафт теории алгоритмов и вычислительной сложности.