On a greedy heuristic for the multicommodity rent-or-buy problem
Çoklu eşya satın al ya da kirala problemine aç gözlü bir sezgisel
- Tez No: 374437
- Danışmanlar: YRD. DOÇ. DR. ALİ ÇİVRİL
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2014
- Dil: İngilizce
- Üniversite: Melikşah Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Elektrik ve Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: Belirtilmemiş.
Özet
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.
Özet (Çeviri)
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.
Benzer Tezler
- Ovulasyon indüksiyonu tedavisinde folliküler gelişimin ultrasonografik takibi
Başlık çevirisi yok
MERİH BAYRAM
Tıpta Uzmanlık
Türkçe
1987
Kadın Hastalıkları ve DoğumGazi ÜniversitesiKadın Hastalıkları ve Doğum Ana Bilim Dalı
DOÇ. DR. MÜLAZIM YILDIRIM
- Çimentonun sertleşmesi üzerinde kimyasal komponentlerin etkisi
Başlık çevirisi yok
NACİYE TÜRKEL
Yüksek Lisans
Türkçe
1986
Kimya MühendisliğiUludağ ÜniversitesiKimya Ana Bilim Dalı
PROF. DR. MUSTAFA CEBE
- İzmir'de bazı yolların kapatılarak yaya bölgeleri oluşturma da kent peyzajını geliştirme açısından yeniden planlanması üzerinde araştırmalar
Başlık çevirisi yok
BAHAR TÜRKYILMAZ
Yüksek Lisans
Türkçe
1985
Şehircilik ve Bölge PlanlamaEge ÜniversitesiŞehir ve Bölge Planlama Ana Bilim Dalı
- Atherosklerotik kalp hastalıklarında risk faktörleri
Risk factors in the coronary artery disease
MURAT SUHER
- Diesel motorları yakıt püskürtme sistemlerinin dinamik simülasyonu
Başlık çevirisi yok
İRFAN KARAGÖZ
Yüksek Lisans
Türkçe
1986
Makine MühendisliğiUludağ ÜniversitesiMakine Mühendisliği Ana Bilim Dalı
PROF. DR. OĞUZ BORAT