Избранные труды. Л.Г. Хачиян

Description

В сборник избранных трудов Л.Г. Хачияна (1952-2005) вошли наиболее значительные работы по сложности задач линейного и математического программирования, а также по теории дуализаиии и генерации. Подробно, в нескольких авторских вариантах, изложен открытый Л.Г. Хачияном полиномиальный алгоритм решения задачи линейного программирования — фундаментальный вклад Л.Г. Хачияна в математическое программирование. Книга будет полезна специалистам в области математического программирования и теории сложности, аспирантам и студентам. От составителя......Page 4 А. С. Немировский. Вместо предисловия......Page 9 Биографическая справка......Page 21 Раздел I. АЛГОРИТМЫ ДЛЯ МАТРИЧНЫХ ИГР......Page 22 О скорости сходимости игровых процессов решения матричных игр......Page 23 Сублинейный приближенный вероятностный алгоритм для матричных игр (совм. с М. Григориадисом)......Page 35 Раздел II. СЛОЖНОСТЬ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ......Page 45 Сложность выпуклых задач вещественного и целочисленного полиномиального программирования......Page 46 Полиномиальный алгоритм в линейном программировании Авторское доказательство полиномиальное™ линейного программирования......Page 196 Полиномиальные алгоритмы в линейном программировании О точном решении систем линейных неравенств и задач линейного программирования......Page 215 Полиномиальная разрешимость выпуклого квадратичного программирования (совм. с М.К. Козловым и С. П. Тарасовым) Метод вписанных эллипсоидов (совм. с С. П. Тарасовым и И. И. Эрлихом)......Page 240 Диагональное шкалирование матриц и линейное программирование (совм. с Б. Калантари)......Page 251 Диагональное шкалирование матриц NP-трудно......Page 258 Сложность полуопределенного программирования (совм. с Л. Порколабом)......Page 264 Целые точки в выпуклых полуалгебраических множествах (совм. с Л. Порколабом)......Page 280 Округление многогранников в вещественной модели вычислений......Page 302 Раздел III. ТЕОРИЯ ДУАЛИЗАЦИИ И ИНКРЕМЕНТАЛЬНОГО ПОРОЖДЕНИЯ......Page 320 В. А. Гурвич. Эффективность алгоритмов и сложность задач перечисления......Page 321 О сложности дуализации монотонных дизъюнктивных нормальных форм {совм. с М. Фредманом)......Page 347 О генерации тупиковых конъюнктивных и дизъюнктивных нормальных форм монотонных булевых функций (совм. с В. А. Гурвичем)......Page 358 Двойственно-ограниченные задачи генерации: порождение ми-нимальных целочисленных решений монотонной системы ли-нейных неравенств {совм. с Е. Борошем, В. А. Гурвичем и др.)......Page 370 Раздел IV. РАЗНОЕ......Page 398 Применение псевдополиномиальных алгоритмов для неко¬торых задач комбинаторной оптимизации с ограничениями (совм. с Ю. Г. Сметаниным)......Page 399 Задача вычисления объема многогранника перечислительно трудна......Page 406 Проводимость цепи Маркова на частичном порядке (совм. с А. В. Карзановым)......Page 409 Циклические игры и нахождение минимаксных средних цик¬лов в ориентированных графах (совм. с В. А. Гурвичем и A. В. Карзановым)......Page 418 Раздел V. MEMORIA......Page 432 B. К. Леонтьев. Чтобы помнили......Page 433 В. Хватал. Вспоминая Леонида Хачияна......Page 435 М. К. Козлов. Особенности национальной науки в эпоху застоя......Page 437 X. Эльбассиони Две лекции Леонида Хачияна......Page 444 В. А. Гурвич. Леонид Хачиян и все-все-все......Page 452 Публикации Л. Г. Хачияна......Page 494