Проблема с K-сервером - K-server problem

Вопрос, Web Fundamentals.svgНерешенная проблема в информатике:
Есть ли -конкурентный алгоритм решения -сервер проблема в произвольном метрическом пространстве?
(больше нерешенных проблем в информатике)

В k-сервер проблема это проблема теоретическая информатика в категории онлайн-алгоритмы, одна из двух абстрактных задач на метрические пространства которые занимают центральное место в теории Конкурентный анализ (другое существо метрические системы задач ). В этой задаче онлайн-алгоритм должен управлять перемещением набора k серверы, представленный как точки в метрическом пространстве, и дескриптор Запросы которые также имеют форму точек в пространстве. По мере поступления каждого запроса алгоритм должен определять, какой сервер перейти в запрошенную точку. Цель алгоритма - сохранить небольшое общее расстояние, на которое перемещаются все серверы, по сравнению с общим расстоянием, на которое серверы могли бы пройти оптимальным противником, который заранее знает всю последовательность запросов.

Проблема была впервые поставлена Марк Манассе, Лайл А. МакГеоч и Дэниел Слейтор (1990). Самый известный открытый вопрос, касающийся k-серверной проблемой является так называемая k-серверная гипотеза, также высказанная Манассе и др. Эта гипотеза утверждает, что существует алгоритм решения k-серверная проблема в произвольной метрическое пространство и для любого числа k серверов, имеющих конкурентное соотношение ровно k. Manasse et al. смогли доказать свою гипотезу, когда k = 2, а для более общих значений k когда метрическое пространство ограничено, чтобы иметь ровно k+1 балл. Чробак и Larmore (1991) доказали гипотезу для древовидной метрики. Частный случай метрики, в которой все расстояния равны, называется метрикой. проблема с подкачкой потому что он моделирует проблему алгоритмы замены страниц в кешах памяти, а также уже известно, что k-конкурентный алгоритм (Sleator и Tarjan 1985). Fiat et al. (1990) впервые доказали, что существует алгоритм с конечным коэффициентом конкуренции для любой постоянной k и любое метрическое пространство, и, наконец, Кутсупиас и Пападимитриу (1995) доказали, что алгоритм рабочих функций (WFA) имеет конкурентное соотношение 2k - 1. Однако, несмотря на усилия многих других исследователей, снижение коэффициента конкуренции до k или обеспечение улучшенной нижней границы остается открытой с 2014 г.. Наиболее распространенный сценарий заключается в том, что алгоритм работы k-конкурентный. В этом направлении в 2000 г. Бартал и Кутсупиас показали, что это верно для некоторых частных случаев (если метрическое пространство представляет собой линию, взвешенную звезду или любую метрику k+2 балла).

В 2011 году рандомизированный алгоритм с конкурентной границей Õ (log2k журнал3n) был найден.[1][2] В 2017 году рандомизированный алгоритм с конкурентной границей O (log6 л) был найден.[3]

пример

Чтобы конкретизировать проблему, представьте, что отправляете техников службы поддержки клиентов к клиентам, когда у них возникают проблемы с их оборудованием. В нашем примере задачи два технических специалиста, Мэри и Ной, обслуживают трех клиентов в Сан-Франциско, Калифорния; Вашингтон, округ Колумбия; и Балтимор, штат Мэриленд. Как k-сервер проблема, серверы - техники, поэтому k = 2, и это проблема с двумя серверами. Вашингтон и Балтимор находятся на расстоянии 35 миль (56 км) друг от друга, а Сан-Франциско - на расстоянии 3 000 миль (4800 км) от обоих, и первоначально Мэри и Ной оба находятся в Сан-Франциско.

Рассмотрим алгоритм назначения серверов для запросов, который всегда назначает ближайший сервер к запросу, и предположим, что каждое утро буднего дня клиент в Вашингтоне нуждается в помощи, в то время как каждый будний день днем ​​клиент в Балтиморе нуждается в помощи, и что клиент в Сан-Франциско никогда не нуждается в помощи. помощь. Затем наш алгоритм назначит один из серверов (скажем, Мэри) в район Вашингтона, после чего он всегда будет ближайшим сервером и всегда будет назначен для всех запросов клиентов. Таким образом, каждый день наш алгоритм несет расходы на поездку между Вашингтоном и Балтимором и обратно, 70 миль (110 км). По прошествии года использования этого шаблона запроса алгоритм проработает 20 500 миль (33 000 км): 3000 для отправки Мэри на Восточное побережье и 17 500 для поездок между Вашингтоном и Балтимором. С другой стороны, оптимальный противник, который знает график будущих запросов, мог бы отправить Мэри и Ноя в Вашингтон и Балтимор соответственно, заплатив один раз за проезд в 6000 миль (9700 км), но при этом избежав любых будущих транспортных расходов. Коэффициент конкуренции нашего алгоритма на этом входе составляет 20 500/6000 или приблизительно 3,4, и, регулируя параметры этого примера, коэффициент конкуренции этого алгоритма можно сделать сколь угодно большим.

Таким образом, мы видим, что всегда назначение ближайшего сервера может быть далеко не оптимальным. С другой стороны, для алгоритма, который не знает будущих запросов, кажется глупым отправлять обоих своих технических специалистов из Сан-Франциско, поскольку следующий запрос может быть в этом городе, и ему придется немедленно отправить кого-то обратно. Кажется, что это сложно или невозможно для k-серверный алгоритм должен хорошо работать по сравнению со своим противником. Однако для задачи с двумя серверами существует алгоритм, который всегда имеет общее расстояние перемещения не более чем в два раза превышающее расстояние противника. kГипотеза -сервер утверждает, что аналогичные решения существуют для проблем с любым большим количеством технических специалистов.

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

  1. ^ http://people.csail.mit.edu/madry/docs/kserver.pdf
  2. ^ http://rjlipton.wordpress.com/2011/11/19/another-annoying-open-problem/
  3. ^ [1] который тесно построен на [2]
  • Чробак, Марек; Лармор, Лоуренс Л. (1991). "Оптимальный онлайн-алгоритм для K-серверы на деревьях ». SIAM Журнал по вычислениям. 20 (1): 144–148. CiteSeerX  10.1.1.53.2395. Дои:10.1137/0220008.
  • Fiat, A .; Rabani, Y .; Равид, Ю. (1990). "Конкурентный k-серверные алгоритмы ». Материалы 31-го ежегодного симпозиума IEEE по основам информатики. С. 454–463.