Efficient algorithms for the minimum cost perfect matching problem on general graphs

Abstract

Ö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. Anahtar Kelimeler: En Küçük Maliyetli Tam Eşleme Problemi, Primal- dual Algoritmalar, Gonca Algoritması, Fibonacci Öbekleri. m

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. Key words: Minimum Cost Perfect Matching Problem, Primal-dual Algo rithms, Blossom Algorithm, Fibonacci Heaps. 11