계량 태스크 시스템

태스크 시스템은 온라인 알고리즘의 가능한 구성 집합을 모델링하는 데 사용되는 수학적 객체입니다.그것들은 다양한 온라인 문제를 모델링하기 위해 Borodin, Linial 및 Saks(1992)에 의해 도입되었다.태스크 시스템은 일련의 상태 및 상태 변경 비용을 결정합니다.태스크 시스템은 각 요구가 상태에 처리 시간을 할당하도록 일련의 요구를 입력으로 취득한다.태스크 시스템을 위한 온라인 알고리즘의 목적은 상태에 대한 태스크 처리 및 상태 변경 비용 때문에 발생하는 전체 비용을 최소화하는 것이다.

상태를 변경하는 비용 함수가 메트릭인 경우 태스크 시스템은 미터법 태스크 시스템(MTS)입니다.이것은 가장 일반적인 유형의 태스크 시스템입니다.미터법 태스크 시스템은 페이징, 목록 액세스 및 k-server 문제(유한 공간)와 같은 온라인 문제를 일반화합니다.

정식 정의

태스크 시스템은 페어$({\displaystyle S,}$ $)$ {$displaystyle (S, d)}$입니다. $여기$서 S ${\displaystyle =}$ { ${\displaystyle {}_{}}$ 1,${\displaystyle {}_{}}$s${\displaystyle {}_{}{2\mathrm{}}_{}}$,${\displaystyle \dots ,}$ ${\displaystyle {}_{}}$ ${\displaystyle n_{}}$ $}$ {$display$ S →\{$1},\dotsc, s_{n}\}$는 상태 $집합$이고${\displaystyle d}$ :${\displaystyle }$S × ${\displaystyle S}$ ${\displaystyle \to }$ $display d:$$S\times$ S$\rightarrow \mathbb {R}$은$$ 거리 함수이다.d$\displaystyle$$$d가$$ 메트릭인 $경우{\displaystyle }$$,{\displaystyle }$(${\displaystyle S}$, d$$) {$displaystyle$ ($S,$d)}은$$ 메트릭 태스크 시스템입니다.태스크 시스템에 대한 입력은 시퀀스 ${\displaystyle {}_{}}$ ${\displaystyle =}$ T${\displaystyle {}_{}{1\mathrm{}}_{}}$, T ${\displaystyle {2\mathrm{}}_{}}$, ${\displaystyle \dots ,}$ ${\displaystyle {}_{}}$l $\$=$T_{1}, T_{2},\dotsc, T_{l}$이며, 각 i ${\display style$ i$\}$에 대해 ${\displaystyle {TI}_{}}$\$display$$style$ T_${i}$는$n$의 $비음성{\displaystyle }$ 프로세스를 결정하는 벡터이다.$ylen}$은$($는) $i번째$ 작업을 처리할 때 표시됩니다.

태스크 시스템의 알고리즘은 상태 순서를 결정하는 스케줄$${\(\$displaystyle \pi)$을 생성합니다.$예$를 들어 ${\displaystyle (}$ (${\displaystyle i}$ ) ${\displaystyle =}$ ${\displaystyle {}_{}}$ \ $displaystyle$\$pi$( i ) =$s$_ {$j$ } means$$ that for for t t t$$${\displaystyle t_{}}$ t t t Ti$${ $displaystyle T_{i}$가 $s_{j$에서 실행됨을 $의미$합니다.스케줄 처리 비용은 c ${\displaystyle o}$ ${\displaystyle \mathrm{s}}$ ${\displaystyle \mathrm{t}}$ (${\displaystyle }$(${\displaystyle }$, ${\displaystyle )}$ ) ${\displaystyle =\underset{}{\overset{}{}}}$ i ${\displaystyle \underset{}{\overset{}{=}}}$ ${\displaystyle \underset{}{\overset{}{1}}\underset{}{\overset{}{}}}$ (${\displaystyle i}$ -${\displaystyle 1}$ )${\displaystyle }$,${\displaystyle t}$ (${\displaystyle }$i${\displaystyle }$) + ${\displaystyle T_{}i}$ (${\displaystyle ）}$。\ $display$style \ $mathrm${ $cost }$ ( \ $pi$, \ $pi$ ) = \ $sum _$ i$$$= 1$^{ l $} d -$ i ( 1 ) 、$+T_{i}(\pi(i))$$}$

알고리즘의 목적은 비용을 최소화할 수 있도록 스케줄을 찾는 것입니다.

이미 알려진 결과

온라인 문제와 마찬가지로 계량 태스크 시스템의 알고리즘을 분석하는 가장 일반적인 척도는 온라인 알고리즘의 성능과 최적의 오프라인 알고리즘의 성능을 비교하는 경쟁 분석입니다.결정론적 온라인 알고리즘의 경우, Borodin 등(1992)으로 인한 경쟁률에 대해 ${\displaystyle \mathrm{2n}}$-$$(\displaystyle $2n-1)$의 엄격한 $경계$가 있다.

랜덤화 온라인 알고리즘의 경우 경쟁률은 $\delta {\displaystyle \mathrm{}(\log n}$n / ${\displaystyle \log \log }$ log${\displaystyle \log }$n $)(\displaystyle \Omega(\log$ n$/\log \log$ n$)},$ O$$${\displaystyle (\log {n\mathrm{}}^{}}$n ) 2$$)(\$display style$O\$left(\log n)\$right$)$로 구분됩니다.하한은 Bartal et al.에 기인한다.(2006,2005).피아트와 멘델(2003)의 성적을 바탕으로 개선한 부벡, 코헨, 리, 리(2018)가 상한가를 기록했다.

다양한 유형의 제한된 메트릭에 대한 많은 결과가 있습니다.

「 」를 참조해 주세요.

• 대항 모델
• 경쟁력 분석
• K서버 문제
• 온라인 알고리즘
• 페이지 치환 알고리즘
• 실시간 컴퓨팅

레퍼런스

• Yair Bartal; Avrim Blum; Carl Burch & Andrew Tomkins (1997). "A polylog(n)-Competitive Algorithm for Metrical Task Systems". Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing. pp. 711–719. doi:10.1145/258533.258667.

• Yair Bartal, Béla Bollobás, Manor Mendel (2006). "Ramsey-type theorems for metric spaces with applications to online problems". Journal of Computer and System Sciences. 72 (5): 890–921. arXiv:cs/0406028. doi:10.1016/j.jcss.2005.05.008.{{cite journal}}: CS1 maint: 여러 이름: 작성자 목록(링크)

• Yair Bartal, Nathan Linial, Manor Mendel, Assaf Naor (2005). "On metric Ramsey-type phenomena". Annals of Mathematics. 162 (2): 643–709. arXiv:math/0406353. doi:10.4007/annals.2005.162.643.{{cite journal}}: CS1 maint: 여러 이름: 작성자 목록(링크)

• Allan Borodin and Ran El-Yaniv (1998). Online Computation and Competitive Analysis. Cambridge University Press. pp. 123–149.
• Allan Borodin, Nati Linial, and Michael Saks (1992). "An optimal online algorithm for metrical task systems". Journal of the ACM. 39 (4): 745–763. doi:10.1145/146585.146588.{{cite journal}}: CS1 maint: 여러 이름: 작성자 목록(링크)

• Amos Fiat & Manor Mendel (2003). "Better Algorithms for Unfair Metrical Task Systems and Applications". 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). "Metrical task systems on trees via mirror descent and unfair gluing". Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms. arXiv:1807.04404.