Systém metrických úloh - Metrical task system
Systémy úloh jsou matematické objekty používané k modelování množiny možných konfigurací online algoritmy. Byli představeni Borodin, Liniální a Saks (1992) k modelování řady online problémů. Systém úloh určuje sadu stavů a nákladů na změnu stavů. Systémy úloh získávají jako vstup posloupnost požadavků, takže každý požadavek přiřazuje časy zpracování stavům. Cílem online algoritmu pro systémy úkolů je vytvořit plán, který minimalizuje celkové náklady vzniklé v důsledku zpracování úkolů s ohledem na stavy a v důsledku nákladů na změnu stavů.
Pokud je nákladová funkce ke změně stavů a metrický, systém úkolů je a systém metrických úloh (MTS). Toto je nejběžnější typ systémů úkolů. Metrické systémy úkolů zobecňují online problémy, jako jsou stránkování, přístup do seznamu a problém k-serveru (v konečných prostorech).
Formální definice
Systém úkolů je pár kde je sada státy a je funkce vzdálenosti. Li je metrika, je metrický systém úkolů. Vstupem do systému úkolů je sekvence takové, že pro každého , je vektorem nezáporné položky, které určují náklady na zpracování pro uvádí při zpracování tého úkolu.
Algoritmus pro systém úloh vytváří plán která určuje posloupnost stavů. Například, znamená, že tého úkolu je spuštěn ve stavu . Náklady na zpracování plánu jsou
Cílem algoritmu je najít takový harmonogram, aby byly minimalizovány náklady.
Známé výsledky
Jako obvykle u online problémů je nejběžnějším měřítkem pro analýzu algoritmů pro systémy metrických úkolů konkurenční analýza, kde je výkon online algoritmu porovnáván s výkonem optimálního offline algoritmu. Pro deterministické online algoritmy existuje úzká vazba na konkurenčním poměru v důsledku Borodin et al. (1992).
U randomizovaných online algoritmů je konkurenční poměr nižší a horní ohraničená . Dolní mez je způsobena Bartalem a kol. (2006,2005). Za horní hranici stojí Bubeck, Cohen, Lee a Lee (2018), kteří si polepšili na základě výsledků Fiata a Mendela (2003).
Existuje mnoho výsledků pro různé typy omezených metrik.
Viz také
- Nepříznivý model
- Konkurenční analýza
- Problém s K-serverem
- Online algoritmus
- Algoritmus nahrazení stránky
- Výpočet v reálném čase
Reference
- Yair Bartal; Avrim Blum; Carl Burch a Andrew Tomkins (1997). "Polylog (n) -konkurenční algoritmus pro metrické úkolové systémy". Sborník z dvacátého devátého výročního sympózia ACM o teorii práce s počítačem. str. 711–719. doi:10.1145/258533.258667.
- Yair Bartal, Béla Bollobás, Manor Mendel (2006). "Věty typu Ramsey pro metrické prostory s aplikacemi pro online problémy". Journal of Computer and System Sciences. 72 (5): 890–921. arXiv:cs / 0406028. doi:10.1016 / j.jcss.2005.05.008.CS1 maint: více jmen: seznam autorů (odkaz)
- Yair Bartal, Nathan Linial, Manor Mendel, Assaf Naor (2005). „K metrickým jevům typu Ramseyho“. Annals of Mathematics. 162 (2): 643–709. arXiv:matematika / 0406353. doi:10,4007 / annals.2005.162.643.CS1 maint: více jmen: seznam autorů (odkaz)
- Allan Borodin a Ran El-Yaniv (1998). Online výpočet a konkurenční analýza. Cambridge University Press. str. 123–149.
- Allan Borodin, Nati Linial, a Michael Saks (1992). Msgstr "Optimální online algoritmus pro metrické systémy úloh". Deník ACM. 39 (4): 745–763. doi:10.1145/146585.146588.CS1 maint: více jmen: seznam autorů (odkaz)
- Amos Fiat & Manor Mendel (2003). "Lepší algoritmy pro nekalé metrické úkolové systémy a aplikace". SIAM J. Comput. 32 (6): 1403–1422. arXiv:cs / 0406034. doi:10.1137 / S0097539700376159.
- Sébastien Bubeck; Michael B. Cohen; James R. Lee & Yin Tat Lee (2019). "Metrické systémy úkolů na stromech pomocí zrcadlového sestupu a nespravedlivého lepení". Sborník příspěvků z třicátého výročního sympózia ACM-SIAM o diskrétních algoritmech. arXiv:1807.04404.