Кармаркар, Нарендра

Нарендра Кармаркар (англ. Narendra Karmarkar; род. 1957) — индийский математик, разработавший алгоритм Кармаркара. Включен в список Института научной информации.

Биография

Нарендра Кармаркар родился в Гвалиоре в семье маратхи. Кармаркар получил диплом бакалавра электротехники Индийского технического института Бомбея в 1978 году, магистра наук в Калифорнийском технологическом институте и кандидата в области компьютерных наук в Калифорнийском университете в Беркли. Он изобрел полиномиальный алгоритм линейного программирования, также известный как метод внутренних точек. Алгоритм является краеугольным камнем в области линейного программирования. Он опубликовал свой знаменитый результат вычислений в 1984 году, когда он работал в Bell Labs в Нью-Джерси. Кармаркар был профессором Института фундаментальных исследований Тата в Мумбаи. В настоящее время он работает над новой архитектурой для суперкомпьютеров. Некоторые его идеи опубликованы на Fab 5-конференции, организованной Массачусетским технологическим институтом центра частиц и атомов.

Кармаркар получил ряд наград за свой алгоритм, среди них:

• премия Paris Kanellakis (за конкретное теоретическое достижение, которое оказало значительное и очевидное влияние на практику вычислений), вручена в 2000 году Ассоциацией вычислительной техники;
• награда Distinguished Alumnus в области компьютерных наук и инженерии Университета Калифорнии (1993);
• Ramanujan Prize за вычисления, вручен Азиатским институтом информатики (1989);
• совместная премия Фалкерсона по дискретной математике, вручена Американским математическим обществом и Обществом математического программирования (1988);
• научный сотрудник Bell Laboratories (1987 -);
• Texas Instruments Founders’ Prize (1986);
• Международная премия для молодых ученых имени Маркони (1985);
• премия Фредерика У. Ланчестера Общества исследования операций Америки за лучшие публикации в области исследования операций (1984);
• премия Национальный научный талант в Математике, Индия (1972).

Работы

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

Алгоритм Кармаркара решает задачи линейного программирования за полиномиальное время. Они представлены «n» переменными и «m» ограничениями. Предыдущий метод решения проблем состоял в представлении тела с «х» сторонами и «у» вершинами, где решение состояло в перемещении от вершины к вершине. Новый метод Кармаркара приближается к решению путем разреза по верх тела в пересечении. Следовательно, сложные задачи оптимизации решаются намного быстрее, используя алгоритм Кармаркара. Практическим примером этого является большая эффективность решения сложной проблемы в связях оптимизационной сети, где решение было сокращено время от нескольких недель до нескольких дней. Таким образом, алгоритм обеспечивает более высокую скорость работы и принятия принципиальных решений. Алгоритм Кармаркара стимулировал развитие ряда других методов внутренней точки, некоторые из которых используются в текущих нормах для решения задач линейного программирования.

См. также

• Линейное программирование

Ссылки

• Distinguished Alumnus 1996 IIT Bombay.
• Article with links IIT Bombay Heritage Fund.