?
Properties and Complexity of Some Superposition Choice Procedures
P. 475-486.
In this paper, the application of two-stage superposition choice procedures to the choice problem when the number of alternatives is too large is studied. Two-stage superposition choice procedures consist in sequential application of two choice procedures where the result of the first choice procedure is the input for the second choice procedures. We focus on the study of properties of such choice procedures and evaluate its computational complexity in order to determine which of two-stage superposition choice procedures can be applied in the case of large amount of alternatives.
ПУБЛИКАЦИЯ ПОДГОТОВЛЕНА ПО РЕЗУЛЬТАТАМ ПРОЕКТА:
В книге
Issue 360: Modelling, Computation and Optimization in Information Systems and Management Sciences. , Metz : Springer, 2015
Швыдун С. В., / Высшая школа экономики. Series WP7 "Математические методы анализа решений в экономике, бизнесе и политике". 2015. No. WP7/2015/07.
Исследуются двухступенчатые процедурывыбора, которые представляют собой суперпозицию двух процедур выбора. Показано, какие из рассматриваемых процедур выбора удовлетворяют существующим нормативным условиям, описывающим, каким образом изменяется конечный выбор при изменении предъявляемого множества альтернатив и оценок альтернатив по критериям. Особое внимание уделяется двухступенчатым процедурам, в основе которых лежат позиционные правила, а также правила, использующие мажоритарное отношение, вспомогательную числовую ...
Добавлено: 20 октября 2015 г.
Малышев Д. С., Пардалос П. О., Optimization Letters 2016 Vol. 10 No. 8 P. 1593-1612
Добавлено: 18 декабря 2015 г.
Complexity function and complexity of validity of modal and superintuitionistic propositional logics
Рыбаков М. Н., Shkatov D., Journal of Logic and Computation 2023 Vol. 33 No. 7 P. 1566-1595
Добавлено: 6 января 2023 г.
Малышев Д. С., Journal of Applied and Industrial Mathematics (перевод журналов "Сибирский журнал индустриальной математики" и "Дискретный анализ и исследование операций") 2012 Vol. 6 No. 1 P. 97-99
Добавлено: 7 декабря 2012 г.
Рубцов А. А., Вялый М. Н., , in : Computer Science – Theory and Applications 13th International Computer Science Symposium in Russia, CSR 2018, Moscow, Russia, June 6–10, 2018, Proceedings. Vol. 10846.: Springer, 2018. P. 295-307.
Добавлено: 21 июня 2018 г.
Шитов Я. Н., American Mathematical Monthly 2016 Vol. 123 No. 1 P. 71-77
We present an infinite sequence of pairs (An, Bn) of chess positions on an n × n board such that (1) there is a legal sequence of chess moves leading from An to Bn and (2) any legal sequence leading from An to Bn contains at least exp(n + o(n)) moves. ...
Добавлено: 23 февраля 2016 г.
Малышев Д. С., Journal of Applied and Industrial Mathematics (перевод журналов "Сибирский журнал индустриальной математики" и "Дискретный анализ и исследование операций") 2020 Vol. 14 No. 4 P. 706-721
Добавлено: 30 января 2021 г.
Малышев Д. С., / Cornell University. Series math "arxiv.org". 2013. No. 1307.0278v1.
Добавлено: 3 октября 2013 г.
Малышев Д. С., Discrete Mathematics and Applications 2010 Vol. 19 No. 6 P. 625-630
Понятие граничного класса — полезный инструмент изучения сложности экстремальных задач на графах. В настоящее время известны один граничный класс для задачи о независимом множестве и три граничных класса для задачи о доминирующем множестве. В настоящей работе доказывается бесконечность множества граничных классов для задачи о 3-раскраске. ...
Добавлено: 25 ноября 2012 г.
Сироткин Д. В., Журнал Средневолжского математического общества 2018 Т. 20 № 2 С. 199-205
Задача о вершинной 3-раекраеке для заданного графа состоит в том, чтобы проверить, можно ли множество его вершин разбить на три подмножества попарно несмежных вершин. Известно, что эта задача является NР-полной в классе планарных графов и что она становится полиномиально разрешимой для плоских триангуляций — планарных графов, у которых все грани (включая и внешнюю) являются треугольниками. ...
Добавлено: 2 июля 2018 г.
Алескеров Ф. Т., Мещерякова Н. Г., Швыдун С. В. и др., , in : 6th International Conference on Computers Communications and Control (ICCCC) 2016. : Oradea : Agora University, 2016. P. 118-123.
Добавлено: 8 июня 2016 г.
Yaroslav Shitov, Linear Algebra and its Applications 2013 Vol. 439 No. 8 P. 2500-2502
We present a reduction which shows that the fooling set number, tropical and determinantal ranks of a Boolean matrix are NP-hard to compute. ...
Добавлено: 11 августа 2013 г.
Рыбаков М. Н., Shkatov D., Journal of Logic and Computation 2021 Vol. 31 No. 2 P. 426-443
Добавлено: 24 сентября 2020 г.
Корпелайнен Н., Лозин В. В., Малышев Д. С. и др., Theoretical Computer Science 2011 No. 412 P. 3545-3554
Понятие граничного свойства графов было недавно введено в качестве релаксации минимального по включению свойства и было применено к нескольким задачам алгоритмической и комбинаторной природы. В настоящей работе мы в начале делаем обзор недавних результатов, связанных с этими понятием, а затем применяем их к двум алгоритмическим задачам: задаче о гамильтоновом цикле и задаче о вершинной k-раскраске. ...
Добавлено: 11 сентября 2012 г.
Мокеев Д. Б., Малышев Д. С., Optimization Letters 2020 Vol. 14 No. 6 P. 1317-1322
Добавлено: 12 марта 2020 г.
Малышев Д. С., 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 г.
Малышев Д. С., Duginov O. I., Journal of Applied and Industrial Mathematics (перевод журналов "Сибирский журнал индустриальной математики" и "Дискретный анализ и исследование операций") 2023 Vol. 17 No. 4 P. 791-801
Добавлено: 16 февраля 2024 г.
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 г.
Малышев Д. С., Дискретный анализ и исследование операций 2012 Т. 19 № 6 С. 37-48
Понятие граничного класса графов является полезным инструментом для анализа вычислительной сложности задач на графах в семействе наследственных классов. В предыдущих работах автора исследовались общие черты и особенности семейств граничных классов графов для задачи о вершинной k-раскраске и ее «предельного варианта» - задачи о хроматическом числе. В данной работе эта проблематика рассматривается применительно к реберному варианту ...
Добавлено: 30 ноября 2012 г.
Сироткин Д. В., Малышев Д. С., Journal of Applied and Industrial Mathematics (перевод журналов "Сибирский журнал индустриальной математики" и "Дискретный анализ и исследование операций") 2018 Vol. 12 No. 4 P. 759-769
Добавлено: 20 ноября 2018 г.
Малышев Д. С., Journal of Applied and Industrial Mathematics (перевод журналов "Сибирский журнал индустриальной математики" и "Дискретный анализ и исследование операций") 2013 Vol. 7 No. 2 P. 221-228
Добавлено: 23 июня 2013 г.
Алексеев В. Е., Лозин В. В., Малышев Д. С. и др., Lecture Notes in Computer Science 2008 Vol. 5162 No. 4 P. 96-107
В работе изучается вычислительная сложность нахождения наибольшего независимого множества вершин в планарных графах. В общем случае данная задача является NP-полной. Однако, при определенных ограничениях она становится полиномиально разрешимой. В работе выявляется графовый параметр, к изменению которого чувствительна сложность задачи и предлагаем несколько отрицательных (об NP-полноте) и положительных (о полиномиальной разрешимости) результатов, обобщающих несколько ранее известных ...
Добавлено: 7 ноября 2012 г.
Малышев Д. С., Дискретная математика 2009 Т. 21 № 4 С. 129-134
Понятие граничного класса — полезный инструмент изучения сложности экстремальных задач на графах. В настоящее время известны один граничный класс для задачи о независимом множестве и три граничных класса для задачи о доминирующем множестве. В настоящей работе доказывается бесконечность множества граничных классов для задачи о 3-раскраске. ...
Добавлено: 25 ноября 2012 г.
Berlin : Springer, 2012
This book constitutes the refereed proceedings of the 23rd Annual Symposium on Combinatorial Pattern Matching, CPM 2012, held in Helsinki, Finalnd, in July 2012.
The 33 revised full papers presented together with 2 invited talks were carefully reviewed and selected from 60 submissions. The papers address issues of searching and matching strings and more complicated patterns ...
Добавлено: 30 октября 2013 г.