Metrik vazifalar tizimi - Metrical task system

Vazifalar tizimlari ning mumkin bo'lgan konfiguratsiya to'plamini modellashtirish uchun foydalaniladigan matematik ob'ektlardir onlayn algoritmlar. Ular tomonidan tanishtirildi Borodin, Linial va Saklar (1992) turli xil onlayn muammolarni modellashtirish uchun. Vazifalar tizimi holatlar majmuini va holatlarni o'zgartirish uchun xarajatlarni aniqlaydi. Vazifa tizimlari har bir so'rov holatlarga ishlov berish vaqtini belgilaydigan tarzda so'rovlar ketma-ketligini oladi. Vazifalar tizimlari uchun onlayn algoritmning maqsadi shtatlarga nisbatan ishlarni bajarish va holatlarni o'zgartirish xarajatlari tufayli yuzaga keladigan umumiy xarajatlarni minimallashtirish jadvalini yaratishdir.

Agar holatlarni o'zgartirish uchun xarajatlar funktsiyasi a metrik, vazifalar tizimi a metrik vazifalar tizimi (MTS). Bu vazifalar tizimlarining eng keng tarqalgan turi.Metrik vazifalar tizimlari kabi onlayn muammolarni umumlashtiradi xotira, ro'yxatga kirish, va k-server muammosi (cheklangan joylarda).

Rasmiy ta'rif

Vazifalar tizimi bu juftlik ${displaystyle (S, d)}$ qayerda ${displaystyle S = {s_ {1}, s_ {2}, dotsc, s_ {n}}}$ to'plamidir davlatlar va ${displaystyle d: S imes Sightarrow mathbb {R}}$ masofaviy funktsiya. Agar ${displaystyle d}$ metrik, ${displaystyle (S, d)}$ metrik vazifalar tizimidir. Vazifalar tizimiga kirish - bu ketma-ketlik ${displaystyle sigma = T_ {1}, T_ {2}, dotsc, T_ {l}}$ har biri uchun shunday ${displaystyle i}$ , ${displaystyle T_ {i}}$ ning vektori ${displaystyle n}$ uchun ishlov berish xarajatlarini belgilaydigan salbiy bo'lmagan yozuvlar ${displaystyle n}$ qayta ishlashda holatlar ${displaystyle i}$ topshiriq.

Vazifalar tizimining algoritmi jadvalni ishlab chiqaradi ${displaystyle pi}$ holatlarning ketma-ketligini belgilaydigan. Masalan; misol uchun, ${displaystyle pi (i) = s_ {j}}$ degan ma'noni anglatadi ${displaystyle i}$ topshiriq ${displaystyle T_ {i}}$ holatida boshqariladi ${displaystyle s_ {j}}$ . Jadvalni qayta ishlash qiymati ${displaystyle mathrm {cost} (pi, sigma) = sum _ {i = 1} ^ {l} d (pi (i-1), pi (i)) + T_ {i} (pi (i)).}$

Algoritmning maqsadi xarajatlarni minimallashtiradigan jadvalni topishdir.

Ma'lum natijalar

Onlayn muammolar uchun odatdagidek metrik vazifalar tizimlari algoritmlarini tahlil qilishning eng keng tarqalgan o'lchovi bu raqobatbardosh tahlil, bu erda onlayn algoritmning ishlashi optimal oflayn algoritmning ishlashi bilan taqqoslanadi. Deterministik onlayn algoritmlar uchun qat'iy chegara mavjud ${displaystyle 2n-1}$ Borodin va boshqalarga bog'liq bo'lgan raqobat nisbati to'g'risida. (1992).

Tasodifiy onlayn algoritmlar uchun raqobatdoshlik koeffitsienti chegaralangan ${displaystyle Omega (log n / log log n)}$ va yuqori chegaralangan ${displaystyle Oleft ((log n) ^ {2} ight)}$ . Pastki chegara Bartal va boshqalarga bog'liq. (2006,2005). Yuqori chegara Bubek, Koen, Li va Li (2018) tufayli Fiat va Mendel (2003) natijalariga ko'ra yaxshilandi.

Cheklangan o'lchovlarning har xil turlari bo'yicha ko'plab natijalar mavjud.

Shuningdek qarang

Adabiyotlar

Yair Bartal; Avrim Blum; Karl Burch va Endryu Tomkins (1997). "Polilog (n) -metrik vazifa tizimlari uchun raqobatdosh algoritm". Kompyuter nazariyasi bo'yicha yigirma to'qqizinchi yillik ACM simpoziumi materiallari. 711-719 betlar. doi:10.1145/258533.258667.

Yair Bartal, Bela Bollobas, Manor Mendel (2006). "Onlayn muammolarga dasturlar bilan metrik bo'shliqlar uchun Ramsey tipidagi teoremalar". Kompyuter va tizim fanlari jurnali. 72 (5): 890–921. arXiv:cs / 0406028. doi:10.1016 / j.jcss.2005.05.008.CS1 maint: bir nechta ism: mualliflar ro'yxati (havola)

Yair Bartal, Natan Linial, Manor Mendel, Assaf Naor (2005). "Metrik Ramsey tipidagi hodisalar to'g'risida". Matematika yilnomalari. 162 (2): 643–709. arXiv:matematik / 0406353. doi:10.4007 / annals.2005.162.643.CS1 maint: bir nechta ism: mualliflar ro'yxati (havola)

Allan Borodin va Ran El-Yaniv (1998). Onlayn hisoblash va raqobatbardosh tahlil. Kembrij universiteti matbuoti. 123-149 betlar.
Allan Borodin, Nati Linial va Maykl Saks (1992). "Metrik vazifa tizimlari uchun maqbul onlayn algoritm". ACM jurnali. 39 (4): 745–763. doi:10.1145/146585.146588.CS1 maint: bir nechta ism: mualliflar ro'yxati (havola)

Amos Fiat va Manor Mendel (2003). "Adolatsiz metrik vazifalar tizimlari va ilovalari uchun yaxshiroq algoritmlar". SIAM J. Comput. 32 (6): 1403–1422. arXiv:cs / 0406034. doi:10.1137 / S0097539700376159.

Sebastien Bubek; Maykl B. Koen; Jeyms R. Li va Yin Tat Li (2019). "Oynaga tushish va adolatsiz yopishtirish orqali daraxtlardagi metrik vazifa tizimlari". Diskret algoritmlar bo'yicha o'ttizinchi yillik ACM-SIAM simpoziumi materiallari. arXiv:1807.04404.