Minimal ağırlıklı dominant alt küme problemi(MADAK) üzerine
On dominating subset with the minimal weight problem (DSMW)
Yazar: BURAK ORDİN
Danışman: DOÇ.DR. URFAT NURİYEV
Ege Üniversitesi / Fen Bilimleri Enstitüsü / Matematik Ana Bilim Dalı
Derece: Doktora, 2004
Konu: Matematik = Mathematics

Özet:
V ÖZET MİNİMAL AĞIRLIKLI DOMİNANT ALT KÜME PROBLEMİ (MADAK) ÜZERİNE ORDİN, Burak Doktora Tezi, Matematik Bölümü Tez Yöneticisi : Doç.Dr.Urfat NURÎYEV Ekim 2004, 140 sayfa Son yıllarda Global Optimizasyon problemleri'nin geniş bir sınıfı için Kesen Açılar Yöntemi (Cutting Angle Method) adında yeni bir yöntem geliştirilmektedir. Bu yöntem iteratif olup her adımında kendisi de yine bir Global Optimizasyon problemi olan bir yardımcı problem'in çözülmesi gerekir. Bu tezde yukarıda ifade edilen Altproblem'e denk, Minimal Ağırlıklı Dominant Alt Küme (MADAK) isimli yeni bir Kombinatoryal Optimizasyon problemi tanımlanmıştır. Problemin özellikleri ortaya konmuş, bu özellikler göz önüne alınarak çözüm algoritmaları önerilmiş ve problemin ekonomik yorumu verilmiştir. Daha sonra MADAK problemi'nin graflarla gösterimi yapılmış ve Altproblem'in çözümü için MADAK problemi yardımıyla çözüm yaklaşımları sunulmuştur. Ayrıca, MADAK problemi'nin Atama problemi'nin genel bir hali olduğu gösterilip, problemin NP-Tam (NP-Complete) ve Güçlü NP-Tam (NP-Complete in the Strong Sense) sınıftan olduğu ispatlanmıştır. Geliştirilen heuristik algoritmalarla yapılan hesaplama denemeleri de yaklaşımın yararlılığını ortaya koymaktadır.. Anahtar sözcükler: Kombinatoryal Optimizasyon, Global Optimizasyon, Kesen Açılar Yöntemi, Minimal Ağırlıklı Dominant Alt Küme Problemi, Heuristik Algoritma, Atama Problemi, Greedy Algoritma, Tepe örtüsü Problemi, Küme Örtüsü Problemi, Ağırlıklı Küme Örtüsü Problemi.

Abstract:
VII ABSTRACT ON DOMINATING SUBSET WITH THE MINIMAL WEIGHT (DSMW) PROBLEM ORDIN, Burak Phd. Thesis, Mathematics Department Supervisor: Associate Professors UrfatNURlYEV October 2004, 140 pages Recently a new method, which is called the Cutting Angle Method (CAM), for solving a broad class of Global Optimization problems has been developed. This is an iterative method and in each iteration of the CAM a Subproblem has to be solved, which is in turn, generally, a global optimization problem. In this thesis it is defined a new combinatorical "Dominating Subset with the Minimal Weight (DSMW)" problem that is equivalent to the above Subproblem and the properties of the problem are investigated. Then it is proposed the algorithms which have a ratio bounds in polynomial time, by using above properties for solving the DSMW problem and the economical interpretations of the problem are given. After that the DSMW problem is presented by graphs and some approaches as using the DSMW problem are expressed for solving the Subproblem. In addition the DSMW problem is expressed as a kind of Assignment problem. It is proved that the DSMW problem is NP- Complete and NP-Complete in the Strong Sense. The computational experiments show the effectiveness of the proposed heuristic algorithms. Key words: Combinatorial Optimization, Global Optimization, Cutting Angle Method, Dominating Subset with the Minimal Weight Problem, Heuristic, Assignment Problem, Greedy Algorithm, Vertex Cover Problem, Set Covering Problem, Weighted Set Covering Problem.