A progressive search algorithm for the minimum hitting set problem

Basit Öğe Kaydı
dc.contributor.authorArslan, Hilal
dc.contributor.authorUğurlu, Onur
dc.contributor.authorAkram, Vahid Khalilpour
dc.contributor.authorEliiyi, Deniz Türsel
dc.date.accessioned2022-02-15T16:57:19Z
dc.date.available2022-02-15T16:57:19Z
dc.date.issued2021
dc.departmentBakırçay Üniversitesien_US
dc.description.abstractGiven a finite universe and a collection of the subsets of the universe, the minimum hitting set of thecollection is the smallest subset of the universe that has non-empty intersection with each set in thecollection. Finding the minimum hitting set is an NP-Hard problem that has many real worldapplications. In this study, we propose a progressive search-based approach to find the minimumhitting set of a given collection. The algorithm starts searching for the hitting sets of size 1 andincrease the expected size of the minimum hitting set by a factor of d. After each unsuccessful search,it increases the expected size by d and generate the candidate sets with the expected size. After eachsuccessful search, the algorithm takes the average of last unsuccessful and successful searches andcontinue the searching with the new expected size. The algorithm terminates when the detectedupper bound coincides with the detected lower bound. The effect of different values for d on theperformance of the algorithm has been experimented on various data sets. Experimental resultsreveal that the proposed method effectively computes the minimum hitting set on real-world dataand random dataset.en_US
dc.description.abstractSonlu bir evren ve evrenin alt kümelerinin bir birleşimi verildiğinde, birleşimin minimum isabet kümesi, birleşimdeki her kümeyle boş olmayan kesişimi olan evrenin en küçük alt kümesidir. Minimum isabet kümesini bulma, birçok gerçek dünya uygulaması olan bir NP-Hard problemidir. Bu çalışmada, verilen bir birleşimin minimum isabet kümesini bulmak için aşamalı arama tabanlı bir yaklaşım öneriyoruz. Algoritma, boyutu 1 olan isabet kümelerini aramayla başlar ve minimum isabet kümesinin beklenen boyutunu d faktörü kadar artırır. Her başarısız aramadan sonra, algoritma beklenen boyutu d kadar artırır ve beklenen boyuta sahip aday kümeleri oluşturur. Her başarılı aramadan sonra, algoritma son başarısız ve başarılı aramaların ortalamasını alır ve yeni beklenen boyutla aramaya devam eder. Algılanan üst sınır, algılanan alt sınırla çakıştığı zaman algoritma sona erer. d faktörünün farklı değerlerinin algoritmanın performansı üzerindeki etkisi çeşitli veri kümeleri üzerinde denenmiştir. Deneysel sonuçlar, önerilen yöntemin gerçek dünya verileri ve rasgele veriler üzerindeki minimum isabet kümesini etkili bir şekilde hesapladığını ortaya koymaktadır.en_US
dc.identifier.doi10.21205/deufmd.2021236914
dc.identifier.endpage874en_US
dc.identifier.issn1302-9304
dc.identifier.issn2547-958X
dc.identifier.issue69en_US
dc.identifier.startpage867en_US
dc.identifier.trdizinid443416en_US
dc.identifier.urihttps://hdl.handle.net/20.500.14034/99
dc.identifier.urihttps://doi.org/10.21205/deufmd.2021236914
dc.identifier.urihttps://search.trdizin.gov.tr/yayin/detay/443416
dc.identifier.volume23en_US
dc.indekslendigikaynakTR-Dizinen_US
dc.language.isoenen_US
dc.relation.journalDokuz Eylül Üniversitesi Mühendislik Fakültesi Fen ve Mühendislik Dergisien_US
dc.relation.publicationcategoryMakale - Ulusal Hakemli Dergi - Kurum Öğretim Elemanıen_US
dc.rightsinfo:eu-repo/semantics/openAccessen_US
dc.titleA progressive search algorithm for the minimum hitting set problemen_US
dc.title.alternativeen_US
dc.typeArticleen_US

Dosyalar

Orijinal paket
Listeleniyor 1 - 1 / 1
Küçük Resim
İsim:
A progressive search algorithm for the minimum hitting set problem.pdf
Boyut:
1.04 MB
Biçim:
Adobe Portable Document Format
Açıklama:
Tam Metin / Full Text
İndir

Koleksiyon

TR-Dizin İndeksli Yayınlar Koleksiyonu
Bilgisayar Mühendisliği Bölümü Koleksiyonu
Endüstri Mühendisliği Bölümü Koleksiyonu
Temel Bilimler Bölümü Bölümü Koleksiyonu