Записки научных семинаров ПОМИ
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Общая информация
Последний выпуск
Архив
Импакт-фактор

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS


Зап. научн. сем. ПОМИ:
Год:
Том:
Выпуск:
Страница:
Найти




Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация

Записки научных семинаров ПОМИ, 2015, том 436, страницы 122–135 (Mi znsl6163)  
Эта публикация цитируется в 2 научных статьях (всего в 2 статьях)

Об одном классе оптимизационных задач, не имеющих эффективно вычислимых оптимальных решений

М. Р. Гаврилович, В. Л. Крепс

Национальный исследовательский университет "Высшая школа экономики", ул. Союза Печатников, д. 16, 190008 С.-Петербург, Россия
PDF полного текста (210 kB) Список цитирования (2)
Список литературы:
PDF
HTML
Аннотация: Как известно, большие случайные структуры имеют неслучайные макроскопические свойства. Мы приводим пример неслучайных свойств для класса больших оптимизационных задач, связанных с вычислительной проблемой $MAX\,FLS^=$ вычисления максимального числа совместных уравнений в данной переопределенной системе линейных уравнений. Для этого класса мы доказываем следующее. Не существует “эффективно вычислимой” оптимальной стратегии. При стремлении размера случайной задачи к бесконечности вероятность того, что равномерная смешанная стратегия оптимальна, стремится к единице. Более того, нет “эффективно вычислимой” стратегии, дающей существенно лучший результат для каждого примера оптимизационной задачи. Библ. – 13 назв.
Ключевые слова: oптимизация, концентрация меры, вероятностно проверяемые доказательства.
Финансовая поддержка Номер гранта
Российский фонд фундаментальных исследований 13-01-00348-a
Исследование проводилось при поддержке Российского фонда фундаментальных исследований, проект 13-01-00348-a.
Поступило: 02.09.2015
Англоязычная версия:
Journal of Mathematical Sciences (New York), 2016, Volume 215, Issue 6, Pages 706–714
DOI: https://doi.org/10.1007/s10958-016-2876-0
Реферативные базы данных:
Тип публикации: Статья
УДК: 519.248.6+519.87+519.876+519.83
Образец цитирования: М. Р. Гаврилович, В. Л. Крепс, “Об одном классе оптимизационных задач, не имеющих эффективно вычислимых оптимальных решений”, Теория представлений, динамические системы, комбинаторные методы. XXV, Зап. научн. сем. ПОМИ, 436, ПОМИ, СПб., 2015, 122–135; J. Math. Sci. (N. Y.), 215:6 (2016), 706–714
Цитирование в формате AMSBIB
\RBibitem{GavKre15}
\by М.~Р.~Гаврилович, В.~Л.~Крепс
\paper Об одном классе оптимизационных задач, не имеющих эффективно вычислимых оптимальных решений
\inbook Теория представлений, динамические системы, комбинаторные методы.~XXV
\serial Зап. научн. сем. ПОМИ
\yr 2015
\vol 436
\pages 122--135
\publ ПОМИ
\publaddr СПб.
\mathnet{http://mi.mathnet.ru/znsl6163}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=3498189}
\transl
\jour J. Math. Sci. (N. Y.)
\yr 2016
\vol 215
\issue 6
\pages 706--714
\crossref{https://doi.org/10.1007/s10958-016-2876-0}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84966601349}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/znsl6163
  • https://www.mathnet.ru/rus/znsl/v436/p122
    • Эта публикация цитируется в следующих 2 статьяx:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    		Записки научных семинаров ПОМИ
    Статистика просмотров:
    Страница аннотации:150
    PDF полного текста:44
    Список литературы:41
     
      Обратная связь:
    		  Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024