Метрическая система задач - Metrical task system

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

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

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

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

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

Цель алгоритма - найти такой график, при котором затраты будут минимальными.

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

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

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

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

Смотрите также

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

Рекомендации

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

• Яир Бартал, Béla Bollobás, Поместье Мендель (2006). «Теоремы типа Рамсея для метрических пространств с приложениями к онлайн-задачам». Журнал компьютерных и системных наук. 72 (5): 890–921. arXiv:cs / 0406028. Дои:10.1016 / j.jcss.2005.05.008.CS1 maint: несколько имен: список авторов (связь)

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

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

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

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