On a greedy heuristic for the Steiner forest problem

Abstract

Steiner ormanı problemi onlarca yıldır yaklaştırma algoritmaları ve kombinatoryel optimizasyon alanındaki önemli NP-Tam problemlerden biridir. Bu çalışmada, Steiner ormanı problemi için minimum bir tarayan ağaç bulma problemini çözen açgözlü algoritmalardan esinlenen üç adet sezgisel algoritma geliştiriyoruz. Rastgele geometrik çizgeler ve gerçek dünya geometrik çizgeleri üzerindeki deneysel sonuçlara göre algoritmalarımız Agrawal, Klein ve Ravi'nin ünlü 2 yaklaşık algoritması ve geniş bir şekilde kullanılan açgözlü sezgisel algoritma ile karşılaştırılabilir kalitede çözümler veriyor. Özellikle, gerçek dünya geometrik çizgeleri için algoritmalarımız benzer maliyetlerle çok daha iyi çalışma zamanı veriyor.

The Steiner forest problem is one of the important NP-Complete problems in the field of approximation algorithms and combinatorial optimization through decades. In this work, we devolop three heuristics for Steiner forest problem inspired by the greedy algorithms for the problem of finding a minimum spanning tree. According to the experimental results on random geometric graphs and real-world geometric graphs, our algorithms yield solutions of comparable quality to that of the famous 2-approximate algorithm of Agrawal, Klein and Ravi, and a widely used greedy heuristic. Especially, for real-world geometric graphs they yield much better running time with similar costs.