Войти
 | Нерешенная проблема в информатике :. Есть ли  -конкурентный алгоритм для решения -серверной задачи в произвольном метрическом пространстве? (больше нерешенных проблем в компьютере наука) |
Проблема kсервера - это проблема теоретической информатики в категории онлайн-алгоритмов, одна из двух абстрактных проблем на метрические пространства, которые являются центральными в теории конкурентного анализа (другим является метрические системы задач ). В этой задаче онлайн-алгоритм должен управлять перемещением набора из k серверов, представленных точками в метрическом пространстве, и обрабатывать запросы, которые также имеют форму точек в пространстве. По мере поступления каждого запроса алгоритм должен определять, какой сервер перейти в запрошенную точку. Цель алгоритма - сохранить небольшое общее расстояние, на которое перемещаются все серверы, по сравнению с общим расстоянием, на которое серверы могли бы пройти оптимальным противником, который заранее знает всю последовательность запросов.
Проблема была впервые поставлена Лайлом А. МакГеочем и Дэниелом Слейтором (1990). Наиболее известный открытый вопрос, касающийся проблемы k-сервера, - это так называемая гипотеза k-сервера, также выдвинутая Манассе и др. Эта гипотеза утверждает, что существует алгоритм для решения проблемы k-серверов в произвольном метрическом пространстве и для любого числа k серверов, которые имеют коэффициент конкуренции ровно k. Manasse et al. смогли доказать свою гипотезу, когда k = 2, и для более общих значений k, когда метрическое пространство ограничено, чтобы иметь ровно k + 1 точку. Чробак и Лармор (1991) доказали гипотезу для древовидной метрики. Особый случай показателей, в которых все расстояния равны, называется проблемой разбиения на страницы, потому что он моделирует проблему алгоритмов замены страниц в кэшах памяти, а также уже известно, что он имеет k-конкурентный алгоритм (Sleator и Tarjan 1985). Fiat et al. (1990) впервые доказали, что существует алгоритм с конечным коэффициентом конкуренции для любой константы k и любого метрического пространства, и, наконец, Кутсупиас и Пападимитриу (1995) доказали, что алгоритм рабочих функций (WFA) имеет коэффициент конкуренции 2k - 1. Однако, несмотря на усилия многих других исследователей, снижение коэффициента конкуренции до kили обеспечение улучшенной нижней границы остается открытым по состоянию на 2014 год. Наиболее распространенным сценарием является то, что алгоритм рабочей функции имеет вид k- конкурентный. В этом направлении в 2000 году Бартал и Кутсупиас показали, что это верно для некоторых частных случаев (если метрическое пространство представляет собой линию, взвешенную звезду или любую метрику из k + 2 точек).
В 2011 году был найден рандомизированный алгоритм с конкурентной границей Õ (logk logn). В 2017 году был найден рандомизированный алгоритм с конкурентной границей O (log k).
Чтобы сделать проблему более конкретной, представьте, что отправка технических специалистов службы поддержки клиентов к клиентам, когда у них возникают проблемы с их оборудование. В нашем примере задачи два технических специалиста, Мэри и Ной, обслуживают трех клиентов в Сан-Франциско, Калифорния; Вашингтон; и Балтимор, штат Мэриленд. Что касается проблемы с 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-сервера утверждает, что аналогичные решения существуют для проблем с любым большим количеством технических специалистов.
