grafik teorisinde all-pairs shortest paths yani bir ağdaki tüm düğüm çiftleri arasındaki en kısa yolları hesaplama problemi. 1996'dan beri süregelen bir sınırın ilk kez kaydırılması, üstelik hızdan ödün vermeden yakın düğümlerde 2-yaklaşım garantisiyle birlikte gelmesi, işin en ilginç tarafı. hindistan teknoloji enstitüsü gandinagar'da doçent olan manoj gupta'nın yöntemi FOCS 2025'te yayımlandı; yani akademik camia bunu ciddiye aldı, ki bu tür sınır kaymaları genelde birkaç yıl sonra pratiğe sızar.
olayın perde arkası şu: 1996'dan beri bilinen sınır, hız ile doğruluk arasında bir takas dayatıyordu. hızlı hesaplayacaksan yakın düğümlerde doğruluktan feragat ediyordun, tam doğruluk istiyorsan hesap patlıyordu. gupta'nın işi bu takası kırıyor gibi görünüyor. 2-yaklaşım garantisi kulağa mütevazı gelebilir ama en kısa yolun iki katına kadar sapma demek, pratikte rota planlamadan sosyal ağ analizine kadar birçok yerde "yeterince iyi" kabul edilen bir eşik. asıl değer, bunu yaparken hızın korunmasında.
beni asıl heyecanlandıran kısım teorik: bir sınırın 29 yıl sonra kayması, o sınırın "doğa kanunu" gibi kabul edildiği bir alanda ne kadar büyük bir zihinsel tıkanıklığı çözdüğünü gösteriyor. yarın öbür gün harita uygulamalarında, lojistik optimizasyonunda ya da dev grafik işleyen sistemlerde bu iyileştirmenin yankısını duyarsak şaşırmam. kaynak: shiftdelete