Author(s): Хачиян Л.Г.
Publisher: МЦНМО
Year: 2009
Language: Russian
Pages: 521
Tags: Математика;Прочие разделы математики;
Обложка ......Page 1
Портрет ......Page 2
Титульный ......Page 3
Содержание ......Page 5
От составителя ......Page 7
А.С.Немировский. Вместо предисловия ......Page 14
Биографическая справка ......Page 26
Раздел I. АЛГОРИТМЫ ДЛЯ МАТРИЧНЫХ ИГР ......Page 27
О скорости сходимости игровых процессов решения матричных игр ......Page 28
Сублинейный приближенный вероятностный алгоритм для матричных игр (совм. с М.Григориадисом) ......Page 40
Раздел II. СЛОЖНОСТЬ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ ......Page 51
Сложность выпуклых задач вещественного и целочисленного полиномиального программирования ......Page 52
Полиномиальный алгоритм в линейном программировании ......Page 204
Авторское доказательство полиномиальности линейного программирования ......Page 209
Полиномиальные алгоритмы в линейном программировании ......Page 226
О точном решении систем линейных неравенств и задач линейного программирования ......Page 246
Полиномиальная разрешимость выпуклого квадратичного программирования (совм. с М.К.Козловым и С.Л.Тарасовым) ......Page 251
Метод вписанных эллипсоидов (совм. с С.П.Тарасовым и И.И.Эрлихом) ......Page 255
Диагональное шкалирование матриц и линейное программирование (совм. с Б. Калантари) ......Page 262
Диагональное шкалирование матриц NP-трудно ......Page 269
Сложность полуопределенного программирования (совм. с Л. Порколабом) ......Page 275
Целые точки в выпуклых полуалгебраических множествах (совм. с Л. Порколабом) ......Page 291
Округление многогранников в вещественной модели вычислений ......Page 313
Раздел III. ТЕОРИЯ ДУАЛИЗАЦИИ И ИНКРЕМЕНТАЛЬНОГО ПОРОЖДЕНИЯ ......Page 331
В.А.Гурвич. Эффективность алгоритмов и сложность задач перечисления ......Page 332
О сложности дуализации монотонных дизъюнктивных нормальных форм (совм. с М.Фредманом) ......Page 358
О генерации тупиковых конъюнктивных и дизъюнктивных нормальных форм монотонных булевых функций (совм. с В.А.Гурвичем) ......Page 369
Двойственно-ограниченные задачи генерации: порождение минимальных целочисленных решений монотонной системы линейных неравенств (с Е.Борошем, В.А.Гурвичем и др.) ......Page 381
Раздел IV. РАЗНОЕ ......Page 409
Применение псевдополиномиальных алгоритмов для некоторых задач комбинаторной оптимизации с ограничениями (совм. с Ю.Г.Сметаниным) ......Page 410
Задача вычисления объема многогранника перечислительно трудна ......Page 417
Проводимость цепи Маркова на частичном порядке (совм. с А. В. Карзановым) ......Page 420
Циклические игры и нахождение минимаксных средних циклов в ориентированных графах (совм. с В.А.Гурвичем и A.В.Карзановым) ......Page 429
Раздел V. MEMORIA ......Page 443
B.К.Леонтьев. Чтобы помнили ......Page 444
В.Хватал. Вспоминая Леонида Хачияна ......Page 446
М.К.Козлов. Особенности национальной науки в эпоху застоя ......Page 448
X.Элъбассиони. Две лекции Леонида Хачияна ......Page 455
В.А.Гурвич. Леонид Хачиян и все-все-все ......Page 464
Публикации Л. Г. Хачияна ......Page 506
Именной указатель ......Page 515
