Система метрических задач

Системы задач — это математические объекты, используемые для моделирования набора возможных конфигураций онлайн-алгоритмов . Они были введены Бородиным , Линиалом и Саксом (1992) для моделирования различных онлайн-задач. Система задач определяет набор состояний и стоимость изменения состояний. Системы задач получают в качестве входных данных последовательность запросов, так что каждый запрос назначает время обработки состояниям. Целью онлайн-алгоритма для систем задач является создание расписания, которое минимизирует общую стоимость, понесенную из-за обработки задач по отношению к состояниям и из-за стоимости изменения состояний.

Если функция стоимости изменения состояний является метрикой , то система задач является метрической системой задач (MTS). Это наиболее распространенный тип систем задач. Метрические системы задач обобщают такие онлайн-задачи, как разбиение на страницы , доступ к спискам и проблема k-сервера (в конечных пространствах).

Система задач — это пара , где — набор состояний , а — функция расстояния. Если — метрика, — метрическая система задач. Входом в систему задач является последовательность, такая что для каждого — вектор неотрицательных записей, которые определяют затраты на обработку состояний при обработке th-й задачи.${\displaystyle (S,d)}$${\displaystyle S=\{s_{1},s_{2},\dotsc ,s_{n}\}}$${\displaystyle d:S\times S\rightarrow \mathbb {R} }$${\displaystyle д}$${\displaystyle (S,d)}$${\displaystyle \sigma =T_{1},T_{2},\dotsc ,T_{l}}$${\displaystyle я}$${\displaystyle T_{i}}$${\displaystyle n}$${\displaystyle n}$${\displaystyle я}$

Алгоритм для системы задач создает расписание , которое определяет последовательность состояний. Например, означает, что th-я задача выполняется в состоянии . Стоимость обработки расписания составляет${\displaystyle \пи}$${\displaystyle \пи (i)=s_{j}}$${\displaystyle я}$${\displaystyle T_{i}}$${\displaystyle s_{j}}$${\displaystyle \mathrm {стоимость} (\pi ,\sigma )=\sum _{i=1}^{l}d(\pi (i-1),\pi (i))+T_{i}(\pi (i)).}$

Цель алгоритма — найти такое расписание, при котором стоимость будет минимальной.

Как обычно для онлайн-задач, наиболее распространенной мерой анализа алгоритмов для метрических систем задач является конкурентный анализ , где производительность онлайн-алгоритма сравнивается с производительностью оптимального офлайн-алгоритма. Для детерминированных онлайн-алгоритмов существует жесткая граница конкурентного отношения, согласно Бородину и др. (1992).${\displaystyle 2n-1}$

Для рандомизированных онлайн-алгоритмов конкурентное отношение ограничено снизу и сверху . Нижняя граница получена Барталом и др. (2006, 2005). Верхняя граница получена Бубеком, Коэном, Ли и Ли (2018), которые улучшили результат Фиата и Менделя (2003).${\displaystyle \Омега (\log n/\log \log n)}$${\displaystyle O\left((\log n)^{2}\right)}$

Существует множество результатов для различных типов ограниченных метрик.

• Модель противника
• Конкурентный анализ
• Проблема с K-сервером
• Онлайн алгоритм
• Алгоритм замены страницы
• Вычисления в реальном времени

• Яир Бартал; Аврим Блюм; Карл Берч и Эндрю Томкинс (1997). «Полилог(n)-конкурентный алгоритм для метрических систем задач». Труды двадцать девятого ежегодного симпозиума ACM по теории вычислений . стр. 711–719. doi : 10.1145/258533.258667 .

• Яир Бартал, Бела Боллобаш , Манор Мендель (2006). «Теоремы типа Рамсея для метрических пространств с приложениями к онлайн-задачам». Журнал компьютерных и системных наук . 72 (5): 890–921. arXiv : cs/0406028 . doi :10.1016/j.jcss.2005.05.008. S2CID  1450455.{{cite journal}}: CS1 maint: несколько имен: список авторов ( ссылка )

• Яир Бартал, Натан Линиал, Манор Мендель, Ассаф Наор (2005). «О метрических явлениях типа Рамсея». Annals of Mathematics . 162 (2): 643–709. arXiv : math/0406353 . doi :10.4007/annals.2005.162.643.{{cite journal}}: CS1 maint: несколько имен: список авторов ( ссылка )

• Аллан Бородин и Ран Эль-Янив (1998). Онлайн-вычисления и конкурентный анализ. Cambridge University Press. С. 123–149.
• Аллан Бородин , Нати Линиал и Майкл Сакс (1992). «Оптимальный онлайн-алгоритм для метрических систем задач». Журнал ACM . 39 (4): 745–763. doi : 10.1145/146585.146588 . S2CID  18783826.{{cite journal}}: CS1 maint: несколько имен: список авторов ( ссылка )

• Амос Фиат и Манор Мендель (2003). «Лучшие алгоритмы для систем и приложений с нечестными метрическими задачами». SIAM J. Comput . 32 (6): 1403–1422. arXiv : cs/0406034 . doi :10.1137/S0097539700376159.

• Бубек, Себастьен; Коэн, Майкл Б.; Р. Ли, Джеймс и Ли, Инь Тат (2019). «Системы метрических задач на деревьях с помощью зеркального спуска и несправедливого склеивания». Труды тридцатого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам . arXiv : 1807.04404 .