Ölçülü görev sistemi - Metrical task system

Görev sistemleri olası konfigürasyon kümesini modellemek için kullanılan matematiksel nesnelerdir çevrimiçi algoritmalar. Tarafından tanıtıldı Borodin, Linial ve Saks (1992) çeşitli çevrimiçi problemleri modellemek için. Bir görev sistemi, durumları değiştirmek için bir dizi durumu ve maliyeti belirler. Görev sistemleri, her bir isteğin durumlara işlem süreleri atayacağı şekilde, girdi olarak bir dizi istek elde eder. Görev sistemleri için çevrimiçi bir algoritmanın amacı, görevlerin durumlara göre işlenmesi ve durumları değiştirme maliyeti nedeniyle ortaya çıkan toplam maliyeti en aza indiren bir program oluşturmaktır.

Durumları değiştirmek için maliyet işlevi bir metrik görev sistemi bir ölçülü görev sistemi (MTS). Bu, en yaygın görev sistemleri türüdür.Metrik görev sistemleri, çevrimiçi sorunları genelleştirir. sayfalama, listeye erişim, ve k-sunucusu sorunu (sonlu uzaylarda).

Resmi tanımlama

Bir görev sistemi bir çifttir ${görüntü stili (S, d)}$ nerede ${displaystyle S = {s_ {1}, s_ {2}, dotsc, s_ {n}}}$ bir dizi eyaletler ve ${displaystyle d: S imes Sightarrow mathbb {R}}$ bir mesafe fonksiyonudur. Eğer ${displaystyle d}$ bir metriktir ${görüntü stili (S, d)}$ ölçülü bir görev sistemidir. Görev sistemine bir girdi, bir dizidir ${displaystyle sigma = T_ {1}, T_ {2}, dotsc, T_ {l}}$ öyle ki her biri için ${displaystyle i}$ , ${displaystyle T_ {i}}$ bir vektör ${displaystyle n}$ için işlem maliyetlerini belirleyen olumsuz olmayan girdiler ${displaystyle n}$ işlerken devletler ${displaystyle i}$ inci görev.

Görev sistemi için bir algoritma bir program oluşturur ${displaystyle pi}$ durumların sırasını belirler. Örneğin, ${displaystyle pi (i) = s_ {j}}$ demek oluyor ki ${displaystyle i}$ görev ${displaystyle T_ {i}}$ durumda çalıştırılır ${displaystyle s_ {j}}$ . Bir programın işlem maliyeti ${displaystyle mathrm {maliyet} (pi, sigma) = toplam _ {i = 1} ^ {l} d (pi (i-1), pi (i)) + T_ {i} (pi (i)).}$

Algoritmanın amacı, maliyeti en aza indirecek bir program bulmaktır.

Bilinen Sonuçlar

Çevrimiçi problemlerde her zaman olduğu gibi, ölçülü görev sistemleri için algoritmaları analiz etmenin en yaygın ölçüsü rekabet Analizi, çevrimiçi bir algoritmanın performansının optimum çevrimdışı algoritmanın performansıyla karşılaştırıldığı yer. Belirleyici çevrimiçi algoritmalar için sıkı bir sınır vardır ${displaystyle 2n-1}$ Borodin ve ark. (1992).

Rastgele çevrimiçi algoritmalar için, rekabetçi oran aşağıdakilerle daha düşük sınırlıdır: ${displaystyle Omega (günlük n / günlük günlük n)}$ ve üst sınırlanmış ${displaystyle Oleft ((log n) ^ {2} ight)}$ . Alt sınır, Bartal ve ark. (2006,2005). Üst sınır, Fiat ve Mendel'in (2003) bir sonucu üzerine gelişen Bubeck, Cohen, Lee ve Lee'den (2018) kaynaklanmaktadır.

Çeşitli kısıtlanmış metrik türleri için pek çok sonuç vardır.

Ayrıca bakınız

Referanslar

Yair Bartal; Avrim Blum; Carl Burch ve Andrew Tomkins (1997). "Metrik Görev Sistemleri için bir polylog (n) -Competitive Algorithm". Yirmi Dokuzuncu Yıllık ACM Bilişim Teorisi Sempozyumu Bildirileri. s. 711–719. doi:10.1145/258533.258667.

Yair Bartal, Béla Bollobás, Manor Mendel (2006). "Çevrimiçi problemlere uygulamalarla metrik uzaylar için Ramsey tipi teoremler". Bilgisayar ve Sistem Bilimleri Dergisi. 72 (5): 890–921. arXiv:cs / 0406028. doi:10.1016 / j.jcss.2005.05.008.CS1 bakım: birden çok isim: yazar listesi (bağlantı)

Yair Bartal, Nathan Linial, Manor Mendel, Assaf Naor (2005). "Metrik Ramsey tipi fenomen üzerine". Matematik Yıllıkları. 162 (2): 643–709. arXiv:matematik / 0406353. doi:10.4007 / annals.2005.162.643.CS1 bakım: birden çok isim: yazar listesi (bağlantı)

Allan Borodin ve Ran El-Yaniv (1998). Çevrimiçi Hesaplama ve Rekabet Analizi. Cambridge University Press. s. 123–149.
Allan Borodin, Nati Linial, ve Michael Saks (1992). "Ölçülü görev sistemleri için en uygun çevrimiçi algoritma". ACM Dergisi. 39 (4): 745–763. doi:10.1145/146585.146588.CS1 bakım: birden çok isim: yazar listesi (bağlantı)

Amos Fiat ve Manor Mendel (2003). "Haksız Metrik Görev Sistemleri ve Uygulamaları için Daha İyi Algoritmalar". SIAM J. Comput. 32 (6): 1403–1422. arXiv:cs / 0406034. doi:10.1137 / S0097539700376159.

Sébastien Bubeck; Michael B. Cohen; James R. Lee ve Yin Tat Lee (2019). "Ayna inişi ve haksız yapıştırma yoluyla ağaçlarda metrik görev sistemleri". Ayrık Algoritmalar Üzerine Otuzuncu Yıllık ACM-SIAM Sempozyumu Bildirileri. arXiv:1807.04404.