?
On the complexity of quasiconvex integer minimization problem
Journal of Global Optimization. 2019. Vol. 73. No. 4. P. 761-788.
Научное направление:
Компьютерные науки
Язык:
английский
Ключевые слова: Nonlinear integer programmingConic functionsQuasiconvex functionsQuasiconvex polynomialsConvex functionsComparison oracleOracle modelComplexity
ПУБЛИКАЦИЯ ПОДГОТОВЛЕНА ПО РЕЗУЛЬТАТАМ ПРОЕКТА:
Грибанов Д. В., Малышев Д. С., Дискретный анализ и исследование операций 2020 Т. 27 № 1 С. 17-42
Рассматривается задача построения последовательных минимумов двумерной целочисленной решётки относительно порядка, заданного некоторой конической функцией f. Для указанной задачи предлагается алгоритм со сложностью 3,32 log_2 R+O(1) обращений к оракулу сравнения функции f, где R - радиус круговой области поиска, тогда как нижняя оценка сложности на данный момент составляет 3 log_2 R+O(1). В настоящей работе приводится эффективный критерий проверки того, что заданные ...
Добавлено: 25 октября 2019 г.
Грибанов Д. В., Малышев Д. С., Journal of Applied and Industrial Mathematics (перевод журналов "Сибирский журнал индустриальной математики" и "Дискретный анализ и исследование операций") 2020 Vol. 14 No. 1 P. 56-72
Добавлено: 3 марта 2020 г.
Грибанов Д. В., Малышев Д. С., , in : Mathematical Optimization Theory and Operations Research, 18th International Conference, MOTOR 2019 Ekaterinburg, Russia, July 8–12, 2019. Vol. 11548.: Springer, 2019. P. 218-231.
Let f:R^n→R be a conic function and x_0∈R^n. In this note, we show that the shallow separation oracle for the set K={x∈R^n:f(x)≤f(x_0)} can be polynomially reduced to the comparison oracle of the function f. Combining these results with known results of D. Dadush et al., we give an algorithm with (O(n))^n*logR calls to the comparison oracle for checking the non-emptiness of the ...
Добавлено: 12 июля 2019 г.
Веселов С. И., Грибанов Д. В., Золотых Н. Ю. и др., Journal of Applied and Industrial Mathematics (перевод журналов "Сибирский журнал индустриальной математики" и "Дискретный анализ и исследование операций") 2018 Vol. 12 No. 3 P. 587-594
Добавлено: 17 февраля 2019 г.
Veselov S. I., Грибанов Д. В., Золотых Н. Ю. и др., Discrete Applied Mathematics 2020 Vol. 283 P. 11-19
Добавлено: 29 октября 2019 г.
St. Petersburg : ACM, 2016
Добавлено: 5 октября 2017 г.
NY : IEEE Computer Society, 2018
WF-IoT 2018, the 4th IEEE World Forum on Internet of Things, is the premier IEEE Forum for the Internet of Things. It is where conference attendees, from around the globe - including research institutes, academia, industry and the public sector -- share their knowledge, expertise and experiences about IoT technologies, applications, economic impacts, and social ...
Добавлено: 14 февраля 2018 г.
Малышев Д. С., / Cornell University. Series math "arxiv.org". 2013. No. 1307.0278v1.
Добавлено: 3 октября 2013 г.
Ясницкий Л. Н., Пермь : Пермский государственный национальный исследовательский университет. – Электронные данные. , 2020
В сборнике представлены материалы Международной конференции «Интеллектуальные системы в науке и технике» и Шестой всероссийской научно-практической конференции «Искусственный интеллект в решении актуальных социальных и экономических проблем ХХI века», которая проводилась 12–18 октября 2020 г. в г. Перми в рамках Пермского естественнонаучного форума «Математика и глобальные вызовы XXI века».
Сборник предназначен для научных и педагогических работников, преподавателей, аспирантов, магистрантов, студентов ...
Добавлено: 4 декабря 2020 г.
Бабаш А. В., М. : ИНФРА-М, РИОР, 2013
Пособие предназначено для студентов высших учебных заведений, обучающихся по специальности «Прикладная информатика (в экономике)». Оно также содержит методический материал для ряда инновационных курсов лекций по профилю «Информационная безопасность» и может быть использовано и для блока дисциплин этого профиля. Ряд представленных результатов полезен специалистам и аспирантам, специализирующихся в указанной области. ...
Добавлено: 14 января 2014 г.
The paper examines the choice problem when the total number of observations and criteria is too large. There are many different procedures, which are used for decision-making process under multiple criteria; however, most of them cannot be applied to large datasets due to their computational complexity while others provide sufficient accuracy. To solve the problem, ...
Добавлено: 20 февраля 2020 г.
Малышев Д. С., Дискретный анализ и исследование операций 2020 Т. 27 № 4 С. 104-130
Задача о рёберной раскраске для заданного графа состоит в том, чтобы минимизировать количество цветов, достаточное для окрашивания его рёбер так, чтобы соседние рёбра были окрашены в разные цвета. Для всех классов графов, определяемых запрещением подграфов с не более чем 6 рёбрами каждый, известен
сложностной статус этой задачи. В настоящей работе данный результат улучшается и получена полная ...
Добавлено: 25 декабря 2020 г.
Грибанов Д. В., Малышев Д. С., Discrete Applied Mathematics 2017 Vol. 227 P. 13-20
Добавлено: 23 апреля 2017 г.
Felikson А. A., Натанзон С. М., Differential Geometry and its Application 2012 Vol. 30 No. 5 P. 490-508
We consider (local) parameterizations of Teichmüller space Tg,n (of genus g hyperbolic surfaces with n boundary components) by lengths of 6 g- 6 + 3 n geodesics. We find a large family of suitable sets of 6 g- 6 + 3. n geodesics, each set forming a special structure called "admissible double pants decomposition". For ...
Добавлено: 5 февраля 2013 г.
Развит метод рандомизированного прогнозирования, основанный на генерации ансамблей энтропийно-оптимальных прогнозных траекторий. Последние генерируются рандомизированными моделями динамической регрессии, содержащими случайные параметры, измерительные шумы и случайный вход. Функции плотности распределения вероятностей случайных параметров и измерительных шумов оцениваются с использованием реальных данных в рамках процедуры рандомизированного машинного обучения. Генерация ансамблей прогнозных траекторий осуществляется путем сэмплирования энтропийно-оптимальных распределений вероятностей. ...
Добавлено: 31 октября 2020 г.
Малышев Д. С., Journal of Applied and Industrial Mathematics (перевод журналов "Сибирский журнал индустриальной математики" и "Дискретный анализ и исследование операций") 2020 Vol. 14 No. 4 P. 706-721
Добавлено: 30 января 2021 г.
Акопов А. С., Beklaryan L. A., Saghatelyan A. K., Environmental Modelling and Software 2019 Vol. 116 P. 7-25
Добавлено: 24 февраля 2019 г.
Lanham : University Press of America, 2012
The history of logic and analytic philosophy in Central and Eastern Europe is still known to very few people. As an exception to the rule, only two scientific schools became internationally popular: the Vienna Circle and the Lvov-Warsaw School. Nevertheless, the countries included in this region have not only joint history, but also joint cultural ...
Добавлено: 13 февраля 2013 г.
Сироткин Д. В., Малышев Д. С., Дискретная математика 2017 Т. 29 № 3 С. 114-125
Задача о независимом множестве для заданного обыкновенного графа состоит в вычислении размера наибольшего множества его попарно несмежных вершин. Предлагается новый способ редукции графов. С его помощью получено новое доказательство NP-полноты задачи о независимом множестве в классе планарных графов и доказана NP-полнота данной задачи в классе плоских графов, имеющих только треугольные внутренние грани, с максимальной степенью ...
Добавлено: 7 сентября 2017 г.
Barcelona : IEEE, 2017
Добавлено: 17 января 2018 г.
Малышев Д. С., Дискретный анализ и исследование операций 2012 Т. 19 № 4 С. 66-72
Рассматривается конструктивный подход к формированию новых случаев эффективной разрешимости задачи о независимом множестве в семействе наследственных частей множества графов Free({P5,C5}). Именно, доказывается, что если эта задача полиномиально разрешима в классе Free({P5,C5,G}), то для любого графа H, который может быть индуктивно получен из G применением к текущему графу сложения с K1 или умножения на K1, эта ...
Добавлено: 31 августа 2012 г.
Красноярск : ИВМ СО РАН, 2013
Труды Пятой Международной конференции «Системный анализ и информационные технологии» САИТ-2013 (19–25 сентября 2013 г., г.Красноярск, Россия): ...
Добавлено: 18 ноября 2013 г.
Малышев Д. С., Discrete Mathematics 2015 Vol. 338 No. 11 P. 1860-1865
We completely determine the complexity status of the 3-colorability problem for hereditary graph classes defined by two forbidden induced subgraphs with at most five vertices. © 2015 Elsevier B.V. All rights reserved. ...
Добавлено: 7 апреля 2014 г.