I detta dokument visar vi lägre gränser för konkurrensförhållandet mellan randomiserade algoritmer för två on-line-problem: K-server-problemet, som föreslagits av [MMS] och ett on-line-rörelseplaneringsproblem på grund av [PY]. Vi bevisar, mot en glömsk motståndare, 1. en (log k) lägre gräns på konkurrensförhållandet för alla randomiserade on-line k-server algoritmer i alla tillräckligt stora metriska utrymme; 2. en (log log k) lägre gräns på konkurrensförhållandet för alla randomiserade on-line k-server algoritmer i varje metriska utrymme med minst k + 1 poäng; och 3. en (log log n) lägre gräns på konkurrensförhållandet för någon online rörelseplanering algoritm för en scen med n hinder. Tidigare, ingen superkonstant lägre gräns på konkurrensförhållandet av randomiserade on-line algoritmer var känd för något av dessa problem.
För k-server-problemet visas en lägre gräns för "log k" (log k) av REF för konkurrensförhållandet mellan randomiserade algoritmer i de vanligaste mätvärdena.
Lower bounds for randomized k -server and motion-planning algorithms
{'venue': "STOC '91", 'journal': None, 'mag_field_of_study': ['Computer Science']}