On a greedy heuristic for the multicommodity rent-or-buy problem

Abstract

Bu tez, ünlü Steiner Ormanı Probleminin genelleştirilmiş bir hali ve önemli bir ağ tasarım problemi olan Çoklu Eşya Kirala veya Satın Al Problemi için üç yeni algoritma öne sürmektedir. Bu algoritmalar Kruskal, Boruvka ve Prim'in iyi billinen minimum yayılan ağaç algoritmalarından esinlenmişlerdir. Bizim algoritmalarımızın son geliştirilen algoritmalara kıyasla kötü olmasına rağmen, bizim algoritmalarımızın özellikle kenar ağırlıklarının yüksek aralıklarla değiştiği çizgelerde iyi bilinen Agrawal, Klein ve Ravi'nin (AKR) algoritmasından çok daha hızlı çalıştığını ve ona benzer sonuç verdiğini gösterdik. Özellikle, algoritmalarımız Öklid düzlemde bir ülkenin şehirlerini birbirine bağlayan gerçek dünya verisi için çok iyi bir alternatif teşkil etmektedirler. . Algoritmalarımızın Steienr Ormanı problemi için çalışma zamanları O((m+n logn )k) olup (2-1⁄k) yaklaşık ve çalışma zamanı O(n^2 logn) olan bir önceki algoritmaya göre daha iyidir ki burada m, n ve k sırası ile çizgedeki köşe, düğüm ve terminal çiftlerinin sayısıdır.

This thesis introduces three new algorithms for an important network design problem called the Multicommodity Rent-or-Buy Problem which is a generalization of the famous Steiner Forest Problem. These algorithms are inspired by the well-known minimum spanning tree algorithms of Kruskal, Prim and Boruvka. Although our algorithms do not have good approximation ratio compared to the state-of-art, we show that they are much faster than the well-known approximation algorithm of Agrawal, Klein and Ravi (AKR) with similar solution costs, especially when the edge weights span a wide range. In particular, our algorithms turn out to be a very good alternative for AKR on real world data, where for example the points to be connected in the problem represents the cities of a country on the Euclidean plane. Thee running time of our algorithms for the Steiner Forest Problem is O((m+n logn )k) which is an improvement over the previous (2-1⁄k) approximate algorithm with O(n^2 logn) running time where m, n and k are the number of edges, vertices and terminal pairs in the graph respectively.