Многоуровневые очереди с обратными связями: различия между версиями

Теорема 2 [3]. Алгоритм RMLF является O (log n log log n)-конкурентным относительно рассеянного соперника. Более того, алгоритм RMLF является O(log n log log n)-конкурентным даже относительно адаптивного соперника при условии, что соперник заранее выбирает все размеры заданий.

Позже Беккетти и Леонарди [ ] показали, что на самом деле RMLF оптимально конкурентоспособен с точностью до постоянного коэффициента. Они также проанализировали RMLF на одинаковых параллельных машинах.

Теорема 3 []. Алгоритм RMLF является O (log n)-конкурентным для одной машины. Для нескольких одинаковых машин RMLF достигает коэффициента конкурентоспособности O(log nlog(mn)), где m – количество машин.