Discrete Applied Mathematics· 2026Q2
Kenar Ağırlıklı Maksimum Klik Problemi İçin Üst Sınırların Sınırsızlığı
Strength of the upper bounds for the Edge-Weighted Maximum Clique Problem
- 0atıf
- Q2SCImago
- 2026yıl
Kısa özet
Kenar Ağırlıklı Maksimum Klik Problemi (EWMCP) için literatürdeki üç ana üst sınırın sınırsız olduğu gösterilmiştir, bu da optimal klik değerini bulmak için bir performans garantisi sağlayamayacakları anlamına gelir.
Yapay zekâ ile başlık ve abstract'tan üretildi; tam metin okunmaz.
Ana noktalar
- EWMCP için üç ana üst sınır, optimal değere oranları sınırsız olabildiği için performans garantisi sunmamaktadır.
- Herhangi iki üst sınır için, birinin diğerinden daha sıkı olduğu özel örnekler mevcuttur.
- Teorik bulgular, DIMACS ve rastgele örnek veri kümeleri üzerindeki hesaplamalı deneylerle doğrulanmıştır.
Yapay zekâ ile başlık ve abstract'tan üretildi; tam metin okunmaz.
Özet (abstract)
We theoretically and computationally compare the strength of the three main upper bounds from the literature on the optimal value of the Edge-Weighted Maximum Clique Problem (EWMCP). We provide a set of instances for which the ratio between any of the three upper bounds and the optimal value of the EWMCP is unbounded, showing that none of them can give a performance guarantee. We further analyze the relative strength among the three upper bounds by determining, for every choice of a ratio between any two of them, the largest values it can attain and providing families of instances for which such values can be reached. Our results show that, for each pair of upper bounds, there exist appropriately chosen instances on which either bound is tighter than the other. Our theoretical analysis is complemented by extensive computational experiments on two benchmark datasets: the standard DIMACS instances and randomly generated instances, providing practical insights into the empirical strength of the upper bounds.
Yazarların özeti; kaynağından alınmıştır. Discrete Applied Mathematics, 2026 · DOI ↗
Ücretsiz hesapla devam et
Makaleye Sor ile bu makaleye günde 3 soru ücretsiz; makaleyi kaydet, kaynakçasını al, ilgi alanına göre her gün yeni özetler. Çıkarımlar Premium.
Web'de ücretsiz devam etGoogle ya da Apple hesabınla giriş; kart istemez. Bu makaleye geri dönersin.
Telefonda:
Alan: Hesaplamalı Kuram ve Matematik
Computational Theory and MathematicsComputer Science