Решение проблемы обеспечения качества дерева многоадресной рассылки услуг
https://doi.org/10.15514/ISPRAS-2021-33(2)-10
Аннотация
В данной статье представлена основанная на потоках формулировка проблемы обеспечения качества дерева многоадресной рассылки услуг в терминах смешанного целочисленного программирования. Это актуальная проблема, связанная с современными телекоммуникационными сетями, обеспечивающие распространение мультимедийного контента через облачные Internet-системы. Насколько нам известно, для проблемы обеспечения качества дерева многоадресной рассылки услуг формулировка в терминах смешанного целочисленного программирования ранее не предлагалась. Экспериментальная оценка выполняется на наборе реалистичных примеров из SteinLib, чтобы показать применимость стандартных точных решателей для нахождения решений реальных задач. Точный метод применяется для бенчмаркинга предлагаемых формулировок, а также для поиска оптимальных или близких к оптимальным решений за приемлемое время исполнения.
Об авторах
Клаудио Энрике РИССО-МОНТАЛЬДО
Республиканский университет
Уругвай
Уругвай
Кандидат наук, научный сотрудник
Франко Рафаэль РОБЛЕДО-АМОЗА
Республиканский университет
Уругвай
Уругвай
Кандидат наук, профессор
Серджо Энрике НЕСМАЧНОВ-КАНОВАС
Республиканский университет
Уругвай
Уругвай
PhD, профессор в Вычислительном центре Института компьютерных наук Инженерного факультета
Список литературы
1. Michel Goemans and Young-Soo Myung. A catalog of Steiner tree formulations. Networks, vol. 23, no.1, 1993, pp. 19-28.
2. Mathias Hauptmann and Marek Karpinski. A Compendium on Steiner Tree Problems. Technical report. Department of Computer Science and Hausdorff Center for Mathematics, University of Bonn, 2014.
3. Marek Karpinski, Ion Mandoiu, Alexander Olshevsky, and Alexander Zelikovsky. Improved Approximation Algorithms for the Quality of Service Multicast Tree Problem. Algorithmica, vol. 42, no. 2, 2005, pp. 109-120.
4. Richard Karp. Reducibility among Combinatorial Problems. In Complexity of Computer Computations. The IBM Research Symposia Series. Springer, 1972, pp. 85-103.
5. Lester Ford and Delbert Fulkerson. Flows in Networks. Princeton University Press, 2010. 212 p.
6. Narendra Karmarkar. A new polynomial-time algorithm for linear programming. Combinatorica, vol. 4, no. 4, 1984, pp. 373-395.
7. Thorsten Koch, Alexander Martin, and Stefan Voß. SteinLib: An Updated Library on Steiner Tree Problems in Graphs. Combinatorial Optimization, vol. 11, 2001, pp. 285-325.
8. Claudio Risso, Sergio Nesmachnow, and Franco Robledo. Mixed Integer Programming Formulations for Steiner Tree and Quality of Service Multicast Tree problems. Programming and Computer Software, vol. 46, no. 8, 2020, pp. 661–678.
Рецензия
Для цитирования:
РИССО-МОНТАЛЬДО К., РОБЛЕДО-АМОЗА Ф., НЕСМАЧНОВ-КАНОВАС С. Решение проблемы обеспечения качества дерева многоадресной рассылки услуг. Труды Института системного программирования РАН. 2021;33(2):163-172. https://doi.org/10.15514/ISPRAS-2021-33(2)-10
For citation:
RISSO-MONTALDO C., ROBLEDO-AMOZA F., NESMACHNOW-CÁNOVAS S. Solving the Quality of Service Multicast Tree Problem. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2021;33(2):163-172. (In Russ.) https://doi.org/10.15514/ISPRAS-2021-33(2)-10
Послать статью по эл. почте 