Minimal ağırlıklı dominant alt küme problemi (madak) üzerine

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.