Yazar
Yazıcı, Volkan, Aykanat, C.
Basım Tarihi
2014
Basım Yeri
-
bilgilendirir
Konu
Kombinatoryal optimizasyon, Grafikler, Buluşsal Yöntem, Optimizasyon, Programlama, Tamsayı
Tür
Süreli Yayın
Dil
İngilizce
Dijital
Evet
Yazma
Hayır
Kütüphane
Özyeğin Üniversitesi
Demirbaş Numarası
1526-5528
Kayıt Numarası
c1a12b34-0a70-4ccd-986e-07966fdaf729
Lokasyon
Bilgisayar Bilimi
Tarih
2014
Notlar
Telif hakkı kısıtlamaları nedeniyle bu makalenin tam metnine erişim yalnızca abonelik yoluyla mümkündür.
Örnek Metin
Çoğaltma, hata toleransı sağlamak, paralelleştirme ve işleme maliyetlerini azaltmak için bilgi alma ve veritabanı sistemlerinde yaygın olarak kullanılan bir tekniktir. Bilgi erişimi ve veri tabanı sistemlerinde ortaya çıkan çeşitli problemler için hipergraf bölümlemeye dayalı kombinatoryal modeller önerilmektedir. Hipergraf bölümlemenin kalitesini artırmak için köşe çoğaltmasının kullanılması olasılığını düşünüyoruz. Bu çalışmada, başlangıçta maksimum çoğaltma kapasitesinin ve başlangıç dengesizlik oranına sahip bir K-yollu hipergraf bölümünün verildiği kısıtlı minimum kesim çoğaltma (CMCR) problemine odaklanıyoruz. CMCR problemindeki amaç, verilen çoğaltma kapasitesi kısıtlaması altında başlangıç dengesizliğinin ya korunduğu ya da azaltıldığı, bölümün ilk kesim boyutunun en aza indirildiği şekilde, verilen bölümün her bir parçası için en uygun köşe çoğaltma kümelerini bulmaktır. Bu çalışmada, CMCR probleminin karmaşıklık analizini sunuyoruz ve kabalaştırma ve tamsayılı doğrusal programlama (ILP) şemalarının benzersiz bir karışımına dayanan bir model öneriyoruz. Bu kabalaştırma algoritması, Dulmage-Mendelsohn ayrıştırmasının yeni bir kullanımından türetilmiştir. Deneyler, Dulmage-Mendelsohn ayrışmasına dayalı kabalaştırma ile birleştirilmiş ILP formülasyonunun, belirli bir K-yollu hipergraf bölümünün kesim boyutunu azaltmak için pratik yürütme sürelerinde yüksek kaliteli sonuçlar sağladığını göstermektedir.
DOI
10.1287/ijoc.2013.0567
Cilt
26
