Метрическая система задач

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

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

Формальное определение

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

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

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

Известные результаты

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

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

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

См. также

Ссылки

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

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

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

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

Амос Фиат и Мэнор Мендель (2003). «Улучшенные алгоритмы для систем и приложений с несправедливыми метрическими задачами». СИАМ Дж. Компьютер . 32 (6): 1403–1422. arXiv : cs/0406034 . дои : 10.1137/S0097539700376159 .

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