Efficient algorithms for the minimum cost perfect matching problem on general graphs
Genel çizelgede en küçük maliyetli tam eşleme problemi için etkin algoritmalar
- Tez No: 28874
- Danışmanlar: DOÇ. DR. MUSTAFA AKGÜL
- Tez Türü: Yüksek Lisans
- Konular: Endüstri ve Endüstri Mühendisliği, İşletme, Industrial and Industrial Engineering, Business Administration
- Anahtar Kelimeler: En Küçük Maliyetli Tam Eşleme Problemi, Primal- dual Algoritmalar, Gonca Algoritması, Fibonacci Öbekleri. m, Algoritmalar, Eşleme algoritmaları, Minimum Cost Perfect Matching Problem, Primal-dual Algo rithms, Blossom Algorithm, Fibonacci Heaps. 11, Algorithms, Matching algorithms
- Yıl: 1993
- Dil: İngilizce
- Üniversite: İhsan Doğramacı Bilkent Üniversitesi
- Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: Belirtilmemiş.
Özet
ÖZET GENEL ÇİZGELERDE EN KÜÇÜK MALİYETLİ TAM EŞLEME PROBLEMİ İÇİN ETKİN ALGORİTMALAR Alper Atamtürk Endüstri Mühendisliği Bölümü Yüksek Lisans Tez Yöneticisi: Doç. Dr. Mustafa Akgül Aralık, 1993 En küçük maliyetli tam eşleme problemi, çözümü için polinom zamanlı algoritmaların bulunduğu ender kombinatoryal en iyileme problemlerinden biridir. Eşleme algoritmaları Postacı Problemi, Yüzeysel Çoklu Mal Akış Problemi ile iyi bilinen Gezgin Satıcı Problemi, Taşıt Çizelgeleme Problemi, Çizge Parçalama Problemi, Küme Parçalama Problemi ve diğerleri için sezgisel yordamlarda kullandır. Bu tez çalışmasında, literatürdeki primal-dual yaklaşımları gözden geçirdikten sonra, en küçük maliyetli tam eşleme probleminin çözümü için iki etkin algoritma sunuyoruz. Her iki algoritmada da tarama, ikil değişken ve indirgenmiş maliyet güncellemesi gibi zaman alıcı işlemlerin sayısında büyük ölçüde indirime gidilmiştir. Detaylı sayısal analizler önerilen algoritmaların rassal olarak üretilen çizgelerde literatürdeki diğer algoritmalardan birçok kat daha hızlı olduklarını göstermiştir. Sonuç olarak, yeni algoritmaların yukarıda değinilen önemli problemlerin çözüm metodlarında kullanıldığında, bunlarda da kayda değer hızlanmaların olabileceğini söyleyebiliriz.
Özet (Çeviri)
ABSTRACT EFFICIENT ALGORITHMS FOR THE MINIMUM COST PERFECT MATCHING PROBLEM ON GENERAL GRAPHS Alper Atamtürk M.S. in Industrial Engineering Supervisor: Assoc. Prof. Mustafa Akgül December, 1993 The minimum cost perfect matching problem is one of the rare combinatorial optimization problems for which polynomial time algorithms exist. Matching algorithms find applications in Postman Problem, Planar Multicommodity Flow Problem, in heuristics to the well known Traveling Salesman Problem, Vehicle Scheduling Problem, Graph Partitioning Problem, Set Partitioning Problem, in VLSI, et cetera. In this thesis, reviewing the existing primal-dual approaches in the literature, we present two efficient algorithms for the minimum cost perfect matching problem on general graphs. In both of the algorithms, we achieved drastic reductions in the total number of time consuming operations such as scanning, updating dual variables and reduced costs. Detailed computational analysis on randomly generated graphs has shown the proposed algorithms to be several times faster than other algorithms in the literature. Hence, we conjecture that employment of the new algorithms in the solution methods of above stated important problems would speed them up significantly.
Benzer Tezler
- Merkezsel ve dışmerkezsel çapraz elemanlı çerçeve yapıların statik ve deprem yüküne göre optimum tasarımı
Optimum desing of concentrically and eccentrically braced frames under static and earthquake loading
F.GÜLTEN GÜLAY
- Doğru akım makinasının adaptif ve optimal kontrolunun pratik gerçeklenmesi
Practical implementation of optimal model reference adaptive control of direct current machine
VEDAT DEVECİ
Yüksek Lisans
Türkçe
1991
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiPROF.DR. M. KEMAL SARIOĞLU
- Lojik devre tasarımı algoritmaları
Başlık çevirisi yok
ORHAN UÇAR
Yüksek Lisans
Türkçe
1996
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiPROF.DR. AHMET DERVİŞOĞLU
- Gezgin satıcı problemi
Traveling salesman problem
VOLKAN M. ÖZALP
Yüksek Lisans
Türkçe
1995
Endüstri ve Endüstri Mühendisliğiİstanbul Teknik ÜniversitesiDOÇ.DR. FÜSUN ÜLENGİN
- Bozulabilir mallar için optimal üretim planlaması
Optimal production planning for decaying items
MELDA GÜRSOY