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, Minimum Cost Perfect Matching Problem, Primal-dual Algo rithms, Blossom Algorithm, Fibonacci Heaps. 11
- 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ı: 65
Ö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
- Algorithms for interference immunity and efficient radio resource utilization in wireless communications systems
Kablosuz iletişim sistemlerinde girişim direnci ve verimli radyo kaynağı kullanımı için algoritmalar
ARMED TUSHA
Doktora
İngilizce
2023
Elektrik ve Elektronik Mühendisliğiİstanbul Medipol ÜniversitesiElektrik-Elektronik Mühendisliği ve Siber Sistemler Ana Bilim Dalı
PROF. DR. HÜSEYİN ARSLAN
- 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
- Ultimate load capacity of optimally designed cellular beams
Optimum boyutlandırılmış dairesel gözenekli petek kirişlerin yük taşıma kapasitesi
FERHAT ERDAL
Doktora
İngilizce
2011
Mühendislik BilimleriOrta Doğu Teknik ÜniversitesiMühendislik Bilimleri Bölümü
PROF. DR. MEHMET POLAT SAKA
PROF. DR. TURGUT TOKDEMİR
- Resource aware distributed detection and estimation of random events in wireless sensor networks
Telsız duyarga agları ıcın rastlantısal olayların kaynak duyarlı dagınık tesbıt ve kestırımı
ENGIN MAŞAZADE
Doktora
İngilizce
2010
Elektrik ve Elektronik MühendisliğiSabancı ÜniversitesiElektronik Mühendisliği Ana Bilim Dalı
DOÇ. DR. MEHMET KESKINOZ
PROF. DR. PRAMOD K. VARSHNEY
- Mikroskobik kanallar üzerinde gerçekleşen ıslanma dinamikleri
Wetting dynamics on microscopic channels
ÖZLEM ÖZTÜRK
Doktora
Türkçe
2020
Fizik ve Fizik Mühendisliğiİstanbul Teknik ÜniversitesiFizik Mühendisliği Ana Bilim Dalı
DOÇ. DR. CEM ÖZGÜR SERVANTİE