Алгоритм Кармаркара

Алгоритм Кармаркара — это алгоритм, представленный Нарендра Кармаркаром в 1984 для решения задач линейного программирования. Это был первый достаточно эффективный алгоритм, который решал задачи за полиномиальное время. Метод эллипсоидов является также алгоритмом полиномиального времени, но он оказался неэффективным в практических приложениях. Если — число переменных и — число бит входных данных, алгоритм Кармаркара требует операций над числами с знаками, в то время как метод эллипсоидов требует таких операций. Время работы алгоритма Кармаркара равно при использовании метода умножения Шёнхаге — Штрассена (см. «O» большое). Алгоритм Кармаркара принадлежит классу методов внутренней точки — текущее допустимое решение не передвигается по границе области допустимых решений как в симплекс-методе, а движется по внутренним точкам области допустимых значений, улучшая с каждой итерацией аппроксимацию оптимального решения определённой дробью и приводя к оптимальному решению с рациональными данными.