Задача о k официантах (The k-server Problem) Алгоритмы обрабатывающие вход по мере поступления Козлов Вадим гр.3539 6 октября 2005 г. - презентация

1 Задача о k официантах (The k-server Problem) Алгоритмы обрабатывающие вход по мере поступления Козлов Вадим гр октября 2005 г.

2 2 Содержание 1. Вступление и постановка задачи 2. Work-Function алгоритм 3. Главные результаты теории

3 Вступление Постановка задачи

4 4 The k-server Problem Постановка задачи В некотором метрическом пространстве k официантов располагаются в конкретных точках Заказы официантам происходят от столиков (точек в пространстве) обслуживаются немедленно: передвижением какого-то официанта в точку заказа Последовательность заказов, где точка в M, конечна, но за ранее не известна Требуется online алгоритм приводящий к минимизации суммарных передвижений

5 5 с-оптимальность Алгоритм А называется с-оптимальным (c-competitive), если для любого r и для любого opt выполняется неравенство cost A (r) < с · cost opt (r) + а где opt – некий оптимальный алгоритм

6 6 The k-server Problem Развитие решающих алгоритмов Сomplicated algorithmk O(k) (Fiat-Rabani-Ravid) Harmonic algorithm2 k (Grove) Work-Function algorithm (WFA)2k - 1 (Koutsoupias-Papadimitriou)

7 Work-Function algorithm

8 8 Work-Function algorithm Определения Состояние системы – множество координат столиков, у которых стоят официанты - последовательность заказов Рабочая функция W r (X) – функция, сопоставляющая состоянию X наименьшую стоимость обслужить r из начального состояния A 0, придя в X Стоимость – суммарное пройденное расстояние. (наименьший путь определяется оптимальным offline алгоритмом, т.е. знающим r)

9 9 Work-Function algorithm Находимся в состоянии X Приходит (i+1)-ый заказ r (ρ=r 1 r 2 …r i - предыдущие) Выбираем такое X', чтобы минимизировать - стоимость оптимального перехода из состояния X в X'

10 Главные результаты теории

11 11 Главные результаты теории 1 Почему достигается минимум Лемма:

12 12 Главные результаты теории 2 заметим

13 13 Главные результаты теории 3 W называется квази выпуклой, если для любого состояния А и В существует биекция h : А > В такая, что для любого разбиения А на мультимножества X и Y, справедливо W(A) + W(B) > W(X + h(Y)) + W(h(X) + Y) Смысл заключается в том, что А можно переделать в В (параллельно переделывая В в А) "маленькими шажками", не увеличивая суммарную работу. Лемма: Все рабочие функции квазивыпуклы

14 14 Главные результаты теории 4 Состояние А назовем минимизатором точки а относительно W, если на нем достигается минимум Лемма: Если А минимизатор для r относительно W ρ, то А минимизатор для r относительно W ρr

15 15 Главные результаты теории 5 Теорема: Work-Function algorithm является (2k-1)-оптимальным, т.е. cost A (r) < (2k-1) · cost opt (r) + а

16 16 Вопросы

17 17 Ссылки Конспект лекций Э.А.Гирша /031210_ pdf Решение задачи n-line/scribes/lec8-9. ps Решение задачи гармоническим методом kserver.ppt