- Код статьи
- S30346444S0002338825050066-1
- DOI
- 10.7868/S3034644425050066
- Тип публикации
- Статья
- Статус публикации
- Опубликовано
- Авторы
- Том/ Выпуск
- Том / Номер выпуска 5
- Страницы
- 78-85
- Аннотация
- Рассматривается задача поиска числа доминирования в процедурах двухуровневого голосования, где на первом этапе голосование проводится в локальных группах агентов, а на втором этапе результаты агрегируются в итоговое решение. Основной целью является определение минимальной доли агентов, поддерживающих предложение, при которой оно может быть принято. Используется метод попарного сходства для анализа структуры задачи и построения эвристических алгоритмов с гарантированной точностью. Рассмотрены три специальных случая: граф связи агентов как дерево, полный граф и регулярный граф с нечетным количеством вершин. Для каждого случая предложены новые эвристические алгоритмы и функции попарного сходства, позволяющие оценить погрешность решения. Результаты работы расширяют применение полиномиальных алгоритмов на более широкий класс задач и предоставляют критерии для выбора оптимального алгоритма на этапе постобработки.
- Ключевые слова
- метод попарного сходства двухуровневое голосование эвристический алгоритм регулярный граф полный граф граф дерево
- Дата публикации
- 09.12.2025
- Год выхода
- 2025
- Всего подписок
- 0
- Всего просмотров
- 23
Библиография
- 1. Breer V.V., Novikov D.A., Rogatkin A.D. Mob Control: Models of Threshold Collective Behavior // 1st Edn. Cham: Springer International Publishing, 2017.
- 2. Chebotarev P., Peleg D. The Power of Small Coalitions Under Two-tier Majority on Regular Graphs // Discrete Applied Mathematics. 2023. V. 340. P. 239–258.
- 3. Broere I., Hattingh J.H., Henning M.A., McRae A.A. Majority Domination in Graphs // Discrete Mathematics. 1995. V. 138. №. 1–3. P. 125–135.
- 4. Yeh H.G., Chang G.J. Algorithmic Aspects of Majority Domination // Taiwanese J. Mathematics. 1997. V. 1. №. 3. P. 343–350.
- 5. Holm T.S. On Majority Domination in Graphs // Discrete Mathematics. 2001. V. 239. №. 1–3. P. 1–12.
- 6. Lemtyuzhnikova D., Chebotarev P., Goubko M., Shushko N. Pairwise Similarity Estimation for Discrete Optimization Problems // Advances in Systems Science and Applications. 2023. V. 23. №. 2. P. 164–177.
- 7. Шушко Н.Н. Метод попарного сходства для задачи двухровневого голосования // Интеллектуализация обработки информации: тез. локл. 15-й междунар. конф. Гродно. ГрГУ Беларусь, 2024.
- 8. Lazarev A.A., Lemtyuzhnikova D.V., Werner F. A Metric Approach for Scheduling Problems with Minimizing the Maximum Penalty // Applied Mathematical Modelling. 2021. V. 89. P. 1163–1176.
- 9. Lazarev A., Lemtyuzhnikova D., Providivets N., Werner F. Polynomially Solvable Subcases for the Approximate Solution of Multi-machine Scheduling Problems // Intern. Conf. on Optimization and Applications. Cham: Springer International Publishing, 2020. P. 211–223.
- 10. Lazarev A.A., Lemtyuzhnikova D.V., Providivets N.A. Metric Approach for Finding Approximate Solutions of Scheduling Problems // Computational Mathematics and Mathematical Physics. 2021. V. 61. P. 1169–1180.
- 11. Bukueva E., Kudinov I., Lemtyuzhnikova D. Analysis of the Feasibility to Use Metric Approach for NP-hard Makespan Minimization Problem // IFAC-PapersOnLine. 2022. V. 55. №. 10. P. 2898–2901.
- 12. Cheng T.C.E., Lazarev A., Lemtyuzhnikova D. A Metric Approach for the Two-station Single-track Railway Scheduling Problem // IFAC-PapersOnLine. 2022. V. 55. №. 10. P. 2875–2880.
