|
Записки научных семинаров ПОМИ, 2015, том 436, страницы 122–135
(Mi znsl6163)
|
|
|
|
Эта публикация цитируется в 2 научных статьях (всего в 2 статьях)
Об одном классе оптимизационных задач, не имеющих эффективно вычислимых оптимальных решений
М. Р. Гаврилович, В. Л. Крепс Национальный исследовательский университет "Высшая школа экономики", ул. Союза Печатников, д. 16, 190008 С.-Петербург, Россия
Аннотация:
Как известно, большие случайные структуры имеют неслучайные макроскопические свойства. Мы приводим пример неслучайных свойств для класса больших оптимизационных задач, связанных с вычислительной проблемой $MAX\,FLS^=$ вычисления максимального числа совместных уравнений в данной переопределенной системе линейных уравнений. Для этого класса мы доказываем следующее. Не существует “эффективно вычислимой” оптимальной стратегии. При стремлении размера случайной задачи к бесконечности вероятность того, что равномерная смешанная стратегия оптимальна, стремится к единице. Более того, нет “эффективно вычислимой” стратегии, дающей существенно лучший результат для каждого примера оптимизационной задачи. Библ. – 13 назв.
Ключевые слова:
oптимизация, концентрация меры, вероятностно проверяемые доказательства.
Поступило: 02.09.2015
Образец цитирования:
М. Р. Гаврилович, В. Л. Крепс, “Об одном классе оптимизационных задач, не имеющих эффективно вычислимых оптимальных решений”, Теория представлений, динамические системы, комбинаторные методы. XXV, Зап. научн. сем. ПОМИ, 436, ПОМИ, СПб., 2015, 122–135; J. Math. Sci. (N. Y.), 215:6 (2016), 706–714
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/znsl6163 https://www.mathnet.ru/rus/znsl/v436/p122
|
Статистика просмотров: |
Страница аннотации: | 144 | PDF полного текста: | 42 | Список литературы: | 39 |
|