Teorik bilgisayar bilimindeki k-sunucu varsayımı kanıtlandı

Araştırmacılar 14 Eylül 2026 tarihinde yayımladıkları çalışmayla çevrim içi algoritmalar alanının temel problemlerinden biri olan k-sunucu varsayımını kanıtladı. Varsayım, deterministik bir çevrim içi algoritmanın her metrik uzayda k rekabet oranına ulaşabileceğini öne sürüyordu. Çalışmada, literatürde uzun süredir incelenen iş fonksiyonu algoritmasının bu koşulu sağladığı gösterildi.

İspat sürecinde iş fonksiyonunun matris tabanlı cebirsel bir temsili kullanıldı. Bu yöntemde bir konfigürasyona ulaşan tüm uygulanabilir yollar matris içine kodlanırken, en uygun maliyet hesaplamalarındaki minimum ve toplama işlemleri biçimsel ifadelerin cebirsel işlemlerine dönüştürüldü. Her bir iş fonksiyonu değeri matrisin k sütununun determinantı ile eşleştirildi ve yeni istekler taban değişimi ile satır yenileme yoluyla sisteme aktarıldı.

Amortize analiz aşamasında ise koordinatları orijinal matrisin ikili çiftlerinden oluşan daha geniş bir matris üzerinden tanımlanan potansiyel fonksiyonu incelendi. Bu matematiksel altyapı sayesinde algoritmanın k katsayısını aşmadığı kesinleşti. Çalışma, kaynak tahsisi ve çevrim içi karar alma algoritmalarının sınırlarını netleştiren teorik bir temel sundu.