Email this article PAIRWISE SIMILARITY METHOD FOR MAJORITY DOMINATION PROBLEM
- Authors: Lemtyuzhnikova D.V.1, Shushko N.I.1
-
Affiliations:
- V.A. Trapeznikov Institute of Control Sciences of Russian Academy of Sciences
- Issue: No 5 (2025)
- Pages: 78-85
- Section: COMPUTER METHODS
- URL: https://journals.rcsi.science/0002-3388/article/view/332748
- DOI: https://doi.org/10.31857/S0002338825050066
- ID: 332748
Cite item
Open Access
Access granted
Subscription Access
Abstract
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.
About the authors
D. V. Lemtyuzhnikova
V.A. Trapeznikov Institute of Control Sciences of Russian Academy of Sciences
Author for correspondence.
Email: darabbt@gmail.com
Moscow, Russia
N. I. Shushko
V.A. Trapeznikov Institute of Control Sciences of Russian Academy of Sciences
Email: shushko.ni@phystech.edu
Moscow, Russia
References
- 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.
Supplementary files
