Академия

Ловаш Ласло

Ловаш Ласло
иностранный член РАН

Академические должности

Должность

Организационная структура

Дата активности

Должность

иностранный член отделения

Организационная структура

Должность

член секции

Профиль

Родился 09.03.1948
Венгрия.
Department of Computer Science, Institute of Mathematics, Eötvös Loránd University, Pázmany Petér sétány 1/C, H-1117 Budapest, Hungary.
Избран в 2006 году.

Иностранный член РАН c 25.05.2006 - Отделение математических наук (Прикладная математика и информатика)
Ловаш создал общий подход к решению задач комбинаторной оптимизации путем сведения к задаче полуопределенного программирования. На основе этого подхода решил ряд трудных комбинаторных задач, разработал быстрые алгоритмы решения задач комбинаторной оптимизации. В частности, им разработан быстрый алгоритм редукции базисов целочисленной решетки, позволивший решить большое число задач дискретной алгоритмики, связанных с алгоритмическими проблемами теории чисел, дискретной геометрии, алгебры, теории графов и др. Разработал метод минимизации субмодулярных функций множеств.
Ловаш внес крупный вклад в теорию графов, теорию гиперграфов, теорию матроидов, теорию жадных алгоритмов оптимизации. Одним из первых разрабатывал вероятностный метод в теории графов (широко известна локальная лемма Ловаша). Своими работами положил начало новой научной дисциплине – топологической комбинаторике. Решил ряд конкретных трудных задач, длительное время остававшихся открытыми, в том числе проблему Бержа о совершенных графах, проблему Шеннона о емкости графов, проблему Кнезера.
В последнее время выполнил большой цикл работ по случайным блужданиям и теории конечных цепей Маркова, циклы работ по приближенным методам решения задач комбинаторной оптимизации, поиска, вероятностным алгоритмам оптимизации, алгоритмической геометрии, теории геометрических графов, работы по коммуникационной сложности, интерактивным системам доказательства и др.

Ключевые слова

комбинаторная оптимизация, дискретная алгоритмика, теория графов, комбинаторика, случайные блуждания

Место работы и должность

Hungarian Academy of Sciences, 1245 Budapest, P.O. Box 1000, Hungary Department of Computer Science, Institute of Mathematics, Eotvos Lorand University, Pázmány Péter Sétány 1/C, H-1117 Budapest, Hungary