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

	Наш адрес: 119991 ГСП-1 Москва В-71, Ленинский просп., 14 Телефон: 938-0309 (Справ. бюро) Факс: (495)954-3320 (Лен.пр.,14), (495)938-1844 (Лен.пр.,32а)	Назад