Properties and Complexity of Some Superposition Choice Procedures

S. Shvydun

?

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.

Язык: английский

Полный текст

Текст на другом сайте

Ключевые слова: superposition Choice Problem Choice Procedures Computational Complexity

ПУБЛИКАЦИЯ ПОДГОТОВЛЕНА ПО РЕЗУЛЬТАТАМ ПРОЕКТА:

Анализ данных и принятие решений в социально-экономических и политических системах (2015)

В книге

Advances in Intelligent Systems and Computing

Issue 360: Modelling, Computation and Optimization in Information Systems and Management Sciences. , Metz: Springer, 2015.

On efficient algorithms for bottleneck path problems with many sources

Kirill V. Kaymakov, Dmitry S. Malyshev, Optimization Letters 2024 Vol. 18 P. 1273–1283

Добавлено: 18 апреля 2024 г.

A complete complexity dichotomy of the edge-coloring problem for all sets of 8-edge forbidden subgraphs

Малышев Д. С., Duginov O. I., Journal of Applied and Industrial Mathematics (перевод журналов "Сибирский журнал индустриальной математики" и "Дискретный анализ и исследование операций") 2023 Vol. 17 No. 4 P. 791–801

Добавлено: 16 февраля 2024 г.

Comparative Analysis of Logic Reasoning and Graph Neural Networks for Ontology-Mediated Query Answering with a Covering Axiom

Герасимова О. А., Макаров И. А., Severin N., IEEE Access 2023 Vol. 11 P. 88074–88086

The problem of query answering over incomplete attributed graph data is a challenging field of database management systems and artificial intelligence. When there are rules on data structure expressed in the form of the ontology, the theoretical complexity of finding exact solution satisfying ontology constraints increases. Logic-based methods use theoretical constructions to obtain efficient rewritings ...

Добавлено: 5 января 2024 г.

The discrete Fourier transform over the binary finite field

Sergei Valentinovich Fedorenko, IEEE Access 2023 Vol. 11 P. 62771–62779

Добавлено: 19 июля 2023 г.

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 г.

Some cases of polynomial solvability of the edge coloring problem that are generated by forbidden 8-edge subcubic forests

Добавлено: 31 декабря 2022 г.

On a Countable Family of Boundary Graph Classes for the Dominating Set Problem

G. S. Dakhno, D. S. Malyshev, Journal of Applied and Industrial Mathematics (перевод журналов "Сибирский журнал индустриальной математики" и "Дискретный анализ и исследование операций") 2023 Vol. 17 No. 1 P. 25–31

Наследственный класс — множество обыкновенных графов, замкнутое относительно удаления вершин, каждый такой класс задается множеством своих минимальных запрещенных порожденных подграфов. Если это множество конечно, то он называется конечно определенным. Понятие граничного класса является полезным инструментом анализа вычислительной сложности задач на графах в семействе конечно определенных классов. Задача о доминирующем множестве для заданного графа состоит в ...

Добавлено: 6 декабря 2022 г.

Comparing the Computational Complexity of Monomials and Elements of Finite Abelian Groups

Кочергин В. В., Moscow University Mathematics Bulletin 2022 Vol. 77 No. 3 P. 113–119

Добавлено: 29 октября 2022 г.

Complexity of finite-variable fragments of propositional temporal and modal logics of computation

Рыбаков М. Н., Shkatov D., Theoretical Computer Science 2022 Vol. 925 P. 45–60

Добавлено: 12 мая 2022 г.

An intractability result for the vertex 3-colourability problem

Malyshev D. S., Приставченко О. В., Optimization Letters 2022 Vol. 16 P. 1403–1409

Добавлено: 25 февраля 2022 г.

On computational complexity of set automata

Рубцов А. А., Вялый М. Н., Information and Computation 2021 Vol. 281 Article 104797

Добавлено: 2 февраля 2022 г.

Proceedings of the 17th International Conference on Principles of Knowledge Representation and Reasoning

Захарьящев М. В., Kontchakov R., Ryzhikov V. и др., The International Joint Conference on Artificial Intelligence (IJCAI), 2020.

Добавлено: 6 ноября 2021 г.

No-Rainbow Problem and the Surjective Constraint Satisfaction Problem

Жук Д. Н., , in: 2021 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS).: [б.и.], 2021. P. 1–7.

Добавлено: 8 сентября 2021 г.

Minimal Taylor Algebras as a Common Framework for the Three Algebraic Approaches to the CSP

Barto L., Brady Z., Bulatov M. и др., , in: 2021 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS).: [б.и.], 2021. P. 1–13.

Добавлено: 8 сентября 2021 г.

On 3-colouring of graphs with short faces and bounded maximum vertex degree

Сироткин Д. В., Малышев Д. С., Lobachevskii Journal of Mathematics 2021 Vol. 42 No. 4 P. 760–766

Добавлено: 5 июня 2021 г.

Efficient solvability of the weighted vertex coloring problem for some two hereditary graph classes

Развенская О. О., Малышев Д. С., Journal of Applied and Industrial Mathematics (перевод журналов "Сибирский журнал индустриальной математики" и "Дискретный анализ и исследование операций") 2021 Vol. 15 No. 1 P. 97–117

Добавлено: 23 апреля 2021 г.

Efficient Algorithm for Finding Roots of Error-Locator Polynomials

Sergei Valentinovich Fedorenko, IEEE Access 2021 Vol. 9 P. 38673–38686

Добавлено: 15 апреля 2021 г.

Complete complexity dichotomy for 7-edge forbidden subgraphs in the edge coloring problem

Малышев Д. С., Journal of Applied and Industrial Mathematics (перевод журналов "Сибирский журнал индустриальной математики" и "Дискретный анализ и исследование операций") 2020 Vol. 14 No. 4 P. 706–721

Добавлено: 30 января 2021 г.

The vertex colourability problem for {claw,butterfly}-free graphs is polynomial-time solvable

Малышев Д. С., Optimization Letters 2021 Vol. 15 No. 2 P. 311–326

Добавлено: 6 января 2021 г.

Low-rank matrix approximation in the infinity norm

Gillis N., Шитов Я. Н., Linear Algebra and its Applications 2019 Vol. 581 P. 367–382

Добавлено: 11 ноября 2020 г.

Efficient solvability of the weighted vertex coloring problem for some hereditary class of graphs with 5-vertex prohibitions

Грибанов Д. В., Малышев Д. С., Мокеев Д. Б., Journal of Applied and Industrial Mathematics (перевод журналов "Сибирский журнал индустриальной математики" и "Дискретный анализ и исследование операций") 2020 Vol. 14 P. 480–489

Добавлено: 30 октября 2020 г.

A Proof of CSP Dichotomy Conjecture

Жук Д. Н., , in: 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS).: IEEE, 2017. P. 331–342.

Добавлено: 29 октября 2020 г.

QCSP monsters and the demise of the Chen Conjecture

Жук Д. Н., Martin B., , in: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing.: Association for Computing Machinery (ACM), 2020. P. 91–104.

Добавлено: 29 октября 2020 г.

Special Issue on Computer Science Symposium in Russia

Springer, 2020.

Добавлено: 27 октября 2020 г.