Efficiency analysis of GREEDI algorithm under delta-matroid constraints for subset selection in distributed systems

Inessa Kulakovska

Abstract


The subject matter of the article is the efficiency analysis of greedy optimization algorithms for subset selection in distributed systems under delta-matroid constraints. The goal is to compare the performance of the classical unconstrained greedy algorithm and the GREEDI algorithm with delta-matroid constraints in terms of solution quality, computational characteristics, and scalability. The tasks to be solved are: to implement both algorithms; to perform simulations on synthetic graph datasets with sizes ranging from 10 to 100 nodes; to benchmark computational efficiency and approximation quality; to analyze the impact of delta-matroid constraints on benefit maximization and distributed execution. The methods used are: graph-based modeling, combinatorial optimization under matroid-type constraints, approximation algorithms, and distributed processing frameworks. The following results were obtained: GREEDI consistently provided higher-benefit subsets compared to the unconstrained greedy algorithm, achieving better trade-offs between execution time and solution quality; the distributed processing framework demonstrated scalability for large datasets and supported real-time responsiveness; performance advantages were more pronounced for larger graphs and higher constraint densities. Conclusions. The scientific novelty of the results obtained is as follows: 1) an experimental validation of the GREEDI algorithm under delta-matroid constraints for distributed subset selection was carried out; 2) the influence of such constraints on approximation quality and computational characteristics was quantified; 3) a scalable real-time processing approach for large graph-structured data was proposed, enabling potential applications in sensor deployment, recommendation systems, feature selection, and cache optimization.

Keywords


delta-matroid constraint; greedy algorithm; subset optimization; distributed system; approximation algorithm; computational efficiency; real-time processing; feature selection; sensor network

Full Text:

PDF

References


Mirzasoleiman, B., Karbasi, A., Sarkar, R., & Krause, A. Distributed submodular maximization: Identifying representative elements in massive data. Journal of Machine Learning Research, 2015, vol. 17, iss. 1, pp. 1–56. Available at: https://www.jmlr.org/papers/volume17/mirzasoleiman16a/mirzasoleiman16a.pdf (accessed August 10, 2025).

Clark, A., Alomari, M., Bushnell, L., & Poovendran, R. Scalable and distributed submodular maximization with matroid constraints. Proc. of the 2015 13th Intl. Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks (WiOpt), 2015, pp. 189–196. DOI: 10.1109/WIOPT.2015.7151087.

Banihashem, K., Biabani, L., Goudarzi, S., Hajiaghayi, M. T., Jabbarzade, P., & Monemizadeh, M. Dynamic algorithms for matroid submodular maximization. arXiv preprint:2306.00959, 2023. DOI: 10.48550/arXiv.2306.00959.

Kia, S. S. Submodular maximization subject to uniform and partition matroids with distributed and privacy-preserving computation. arXiv preprint:2501.01071, 2025. DOI: 10.48550/arXiv.2501.01071.

Wahlström, M. Representative set statements for delta-matroids and the Mader delta-matroid. Proc. of SODA, 2024, pp. 780–810. DOI: 10.1137/1.9781611977912.

Oxley, J. Matroid Theory. Oxford University Press, 2011.

Schrijver, A. Combinatorial Optimization: Polyhedra and Efficiency. Algorithms and combinatorics. Springer, 2003.

Koana, T., & Wahlström, M. Faster algorithms on linear delta-matroids. Proc. of the 42nd Intl. Symposium on Theoretical Aspects of Computer Science (STACS 2025), 2025, vol. 327, article no. 62, pp. 62:1–62:19. Available at: https://drops.dagstuhl.de/storage/00lipics/lipics-vol327-stacs2025/LIPIcs.STACS.2025.62/LIPIcs.STACS.2025.62.pdf (accessed August 10, 2025).

Barbosa, M., Ene, A., & Nguyen, H. L. Scalable and distributed greedy algorithms for submodular maximization. Advances in Neural Information Processing Systems (NeurIPS), 2020. Available at: https://proceedings.neurips.cc/paper_files/paper/2020/file/3e7b8e6e3e3c3f3e3e3c3f3e3e3c3f3e-Paper.pdf (accessed August 10, 2025).

Chen, S., Wei, H., Li, Y., & Li, Y. Submodular optimization over streams with inhomogeneous decays. Advances in Neural Information Processing Systems (NeurIPS), 2021. Available at: https://proceedings.neurips.cc/paper_files/paper/2021/file/stream-decay-submodular.pdf (accessed August 10, 2025).

Clark, A., Alomair, B., Bushnell, L., & Poovendran, R. Global practical node and edge synchronization in Kuramoto networks: A submodular optimization framework. arXiv preprint:1411.5797v1, 2021. Available at: https://arxiv.org/pdf/1411.5797v1 (accessed September 8, 2025).

Eiben, K., Koana, T., & Wahlström, M. FPT algorithms over linear delta-matroids with applications. arXiv preprint: 2502.13654, 2025. Available at: https://arxiv.org/abs/2502.13654 (accessed September 8, 2025).

Eiben, K., Koana, T., & Wahlström, M. Determinantal sieving. Proc. of the 2024 ACM-SIAM Symposium on Discrete Algorithms (SODA), 2024, pp. 377–423.

Malenza, G., Garcia, A. M., Birke, R., Benini, L., & Aldinucci M. Analysis of model parallelism for AI applications on a 64-core RV64 server CPU. Intl. Journ. of Parallel Progr., 2025, vol. 53, article no. 27. DOI: 10.1007/s10766-025-00802-6.

Chun, C. Delta-matroids: Origins. The Matroid Union, July 13, 2016. Available at: https://matroidunion.org/?p=1882 (accessed August 10, 2025).

Kulakovska, I. Hrafovyy matroyid ta analiz spanuyuchykh derev u hrafi [Graph matroid and analysis of sleeping trees in a graph]. Modern engineering and innovative technologies, 2025, no. 40-02, pp. 21-31. DOI: 10.30890/2567-5273.2025-40-02. (In Ukrainian).

Zhuravska, I. M., Koretska, O. O., Musiyenko, M. P., Surtel, W. Assembay, A., & et al. Self-powered information measuring wireless networks using the distribution of tasks within multicore processors. Photonics Applications in Astronomy, Communications, Industry, and High Energy Physics Experiments : Proc. of SPIE – International Society for Optics and Photonics, Wilga, Poland, May 28–June 06, 2017, vol. 10445, UNSP 1044527, pp. 1–13. DOI: 10.1117/12.2280965.

Zhuravska, I. & Obukhova, K. Modeling of multi-core power consumption during online video conference. Proc. of the Intelligent Data Acquisition and Advanced Computing Systems: Technology and Applications (IDAACS’2021), Cracow, Poland, Sept. 22–25, 2021, vol. 2, pp. 640–646. DOI: 10.1109/IDAACS53288.2021.9660941.

Tetteh, E. T., & Zielosko, B. Greedy Algorithm for Deriving Decision Rules from Decision Tree Ensembles. Entropy, 2025, vol. 27, iss. 1, article no. 35. DOI: 10.3390/e27010035.

Bodolică, M.-C., Andrușcă, M., Adam, M., & Anton, A. An Efficient Improved Constrained Greedy Optimization Algorithm for Phase Load Balancing in Low-Voltage Distribution Networks. Mathematics, 2025, vol. 13, iss. 22, article no. 3584. DOI: 10.3390/math13223584.

Sun, X., Xu, D., Guo, L., & Li,. M. Deterministic approximation algorithms for matroid constraints Theoretical Computer Science, 2021, vol. 890, pp. 1-15, DOI: 10.1016/j.tcs.2021.08.012.




DOI: https://doi.org/10.32620/reks.2025.4.05

Refbacks

  • There are currently no refbacks.