电邮这篇文章 PAIRWISE SIMILARITY METHOD FOR MAJORITY DOMINATION PROBLEM
- 作者: Lemtyuzhnikova D.V.1, Shushko N.I.1
-
隶属关系:
- V.A. Trapeznikov Institute of Control Sciences of Russian Academy of Sciences
- 期: 编号 5 (2025)
- 页面: 78-85
- 栏目: COMPUTER METHODS
- URL: https://journals.rcsi.science/0002-3388/article/view/332748
- DOI: https://doi.org/10.31857/S0002338825050066
- ID: 332748
如何引用文章
开放存取
##reader.subscriptionAccessGranted##
订阅存取
详细
The paper considers the problem of finding the number of dominant voters in two-level voting procedures. At the first stage, voting is conducted among local groups of voters, and at the second stage, the results are aggregated to form a final decision. The goal is to determine the minimum proportion of voters supporting a proposal for it to be accepted. The paper uses the method of pairwise comparisons to analyze the structure of the problem and develop heuristic algorithms with guaranteed accuracy. Special cases are considered, including the agent communication graph as a tree, complete graph, or regular graph with an odd number of vertices. New heuristic algorithms are proposed for each case, along with pairwise comparison functions to estimate the accuracy of the solution. Results extend the use of polynomial algorithms to a broader class of problems, providing criteria for selecting the optimal algorithm during the post-processing stage.
作者简介
D. Lemtyuzhnikova
V.A. Trapeznikov Institute of Control Sciences of Russian Academy of Sciences
编辑信件的主要联系方式.
Email: darabbt@gmail.com
Moscow, Russia
N. Shushko
V.A. Trapeznikov Institute of Control Sciences of Russian Academy of Sciences
Email: shushko.ni@phystech.edu
Moscow, Russia
参考
- Breer V.V., Novikov D.A., Rogatkin A.D. Mob Control: Models of Threshold Collective Behavior // 1st Edn. Cham: Springer International Publishing, 2017.
- 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.
- 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.
- Yeh H.G., Chang G.J. Algorithmic Aspects of Majority Domination // Taiwanese J. Mathematics. 1997. V. 1. №. 3. P. 343–350.
- Holm T.S. On Majority Domination in Graphs // Discrete Mathematics. 2001. V. 239. №. 1–3. P. 1–12.
- 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.
- Шушко Н.И. Метод попарного сходства для задачи двухуровневого голосования // Интеллектуализация обработки информации: тез. докл. 15-й междунар. конф. Гродно. ГрГУ Беларусь, 2024.
- 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.
- Lazarev A., Lemtyuzhnikova D., Pravdivets 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.
- Lazarev A.A., Lemtyuzhnikova D.V., Pravdivets N.A. Metric Approach for Finding Approximate Solutions of Scheduling Problems // Computational Mathematics and Mathematical Physics. 2021. V. 61. P. 1169–1180.
- 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.
- 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.
补充文件
