In the search of optimal tree networks: Hardness and heuristics
Martynov P, Buzdalov M, Pankratov S, Aksenov V, Schmid S. 2025. In the search of optimal tree networks: Hardness and heuristics. Proceedings of the 2025 Genetic and Evolutionary Computation Conference. GECCO: Genetic and evolutionary computation conference, 249–257.
Download
Conference Paper
| Published
| English
Scopus indexed
Author
Martynov, Pavel;
Buzdalov, Maxim;
Pankratov, SergeiISTA;
Aksenov, Vitaliy;
Schmid, Stefan
Department
Abstract
Traffic in datacenters may follow some pattern: some pairs of servers communicate more frequently than others. Demand-oblivious networks may perform poorly for such workloads, and demand-aware networks optimized for traffic should be used instead. Unfortunately, not all shapes of networks are feasible in real hardware. Practical limitations are usually provided in the form of a topology. For example, a network may be required to be a binary tree, a bounded-degree graph or a Fat tree.
In this work, we consider a topology of a binary tree, one of the most fundamental network topologies. We show that already finding an optimal demand-aware binary tree network is NP-hard. Then, we explore how various optimization techniques, including simple local searches, as well as deterministic mutation and crossover operators, cope with generating efficient tree networks on real-life and synthetic workloads.
Publishing Year
Date Published
2025-07-13
Proceedings Title
Proceedings of the 2025 Genetic and Evolutionary Computation Conference
Publisher
Association for Computing Machinery
Acknowledgement
Research was supported by the German Research Foundation (DFG), grant 470029389 (FlexNets).
Page
249-257
Conference
GECCO: Genetic and evolutionary computation conference
Conference Location
Malaga, Spain
Conference Date
2025-07-14 – 2025-07-18
ISBN
IST-REx-ID
Cite this
Martynov P, Buzdalov M, Pankratov S, Aksenov V, Schmid S. In the search of optimal tree networks: Hardness and heuristics. In: Proceedings of the 2025 Genetic and Evolutionary Computation Conference. Association for Computing Machinery; 2025:249-257. doi:10.1145/3712256.3726425
Martynov, P., Buzdalov, M., Pankratov, S., Aksenov, V., & Schmid, S. (2025). In the search of optimal tree networks: Hardness and heuristics. In Proceedings of the 2025 Genetic and Evolutionary Computation Conference (pp. 249–257). Malaga, Spain: Association for Computing Machinery. https://doi.org/10.1145/3712256.3726425
Martynov, Pavel, Maxim Buzdalov, Sergei Pankratov, Vitaliy Aksenov, and Stefan Schmid. “In the Search of Optimal Tree Networks: Hardness and Heuristics.” In Proceedings of the 2025 Genetic and Evolutionary Computation Conference, 249–57. Association for Computing Machinery, 2025. https://doi.org/10.1145/3712256.3726425.
P. Martynov, M. Buzdalov, S. Pankratov, V. Aksenov, and S. Schmid, “In the search of optimal tree networks: Hardness and heuristics,” in Proceedings of the 2025 Genetic and Evolutionary Computation Conference, Malaga, Spain, 2025, pp. 249–257.
Martynov P, Buzdalov M, Pankratov S, Aksenov V, Schmid S. 2025. In the search of optimal tree networks: Hardness and heuristics. Proceedings of the 2025 Genetic and Evolutionary Computation Conference. GECCO: Genetic and evolutionary computation conference, 249–257.
Martynov, Pavel, et al. “In the Search of Optimal Tree Networks: Hardness and Heuristics.” Proceedings of the 2025 Genetic and Evolutionary Computation Conference, Association for Computing Machinery, 2025, pp. 249–57, doi:10.1145/3712256.3726425.
All files available under the following license(s):
Creative Commons Attribution 4.0 International Public License (CC-BY 4.0):
Main File(s)
File Name
2025_GECCO_Martynov.pdf
609.00 KB
Access Level

Date Uploaded
2025-09-02
MD5 Checksum
7e513fa508cff7e8a0d33f50b1fe09af