Задача о k официантах

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

Задачу первыми поставили Марк Манассе, Лайл А. Макгиох и Дениэль Слитор (1990). Наиболее известным открытым вопросом относительно задачи о k официантах является так называемая гипотеза о k официантах, которую также высказали Манассе, Макгиох и Слитор. Эта гипотеза утверждает, что существует алгоритм решения задачи о k официантах в произвольном метрическом пространстве и для любого числа k исполнителей, и этот алгоритм имеет уровень эффективности в точности k. Манассе и др. смогли доказать гипотезу для k=2 и для более общих значений k, когда метрическое пространство ограничено в точности k+1 точками. Хробак и Лармор (1991) доказали гипотезу для трёх метрик. Частный случай метрики, в которой все расстояния равны, называется задачей кеширования страниц, поскольку он моделирует задачу замещения страниц в кеше, и уже известно, что задача имеет k-эффективный алгоритм (Слитор и Тарьян 1985). Фиат и др. (1990) первыми доказали, что существует алгоритм с конечным уровнем эффективности для некоторой константы k и любого метрического пространства, и, наконец, Коутсоупиас и Пападимитриу (1995) доказали, что Алгоритм Рабочей Функции (АРФ, en:Work-Function Algorithm, WFA) имеет уровень эффективности 2k — 1. Однако, несмотря на попытки многих других исследователей, вопрос уменьшение уровня эффективности до k или достижения лучшей нижней границы остаётся открытым на 2014 год. Исследователи считают, что наиболее вероятный сценарий — Алгоритм Рабочей Функции k-эффективен. В 2000-м году Бартал и Коутсоупиас показали, что предположение верно для некоторых частных случаев (если метрическое пространство является прямой, взвешенной звездой или любой метрикой на k+2 точках).

В 2011 был найден рандомизированный алгоритм с границей эффективности Õ(log²k log³n)^[1]

Чтобы сделать задачу более конкретной, представим посылку технического персонала клиенту, когда клиент имеет проблемы на оборудовании. В нашем примере задача имеет двух техников, Мэри и Ноя, обслуживающих трёх клиентов в Сан-Франциско, Вашингтоне и Балтиморе. В терминах задачи о k официантах исполнителями служат техники, так что k=2 и это задача о 2 официантах. Вашингтон и Балтимор находятся на расстоянии 37 миль друг от друга, в то время как Сан-Франциско удалён на 2425 миль от них обоих. Первоначально Мэри и Ной находятся в Сан-Франциско.

Представим алгоритм для назначения исполнителей запросам, который всегда назначает ближайшего исполнителя для обработки поступившего запроса. Предположим также, что каждое утро рабочего дня клиенту в Вашингтоне нужна помощь, в то время как пополудни каждого дня помощь ожидает клиент в Балтиморе. Клиент в Сан-Франциско никогда помощь не запрашивает. Тогда наш алгоритм будет назначать одного исполнителя, скажем, Мэри, в Вашингтон, после чего она всегда будет ближайшим исполнителем к очередному запросу. Таким образом, каждый день наш алгоритм повлечёт расходы переезда от Вашингтона до Балтимора и обратно, 74 мили. После года работы алгоритма потребуется проехать около 12100 миль — 2425 мили нужно проехать, чтобы добраться с западного побережья, и примерно 9646 миль нужно проехать, чтобы поочерёдно обслуживать клиентов в Вашингтоне и Балтиморе. С другой стороны, оптимальной стратегией, если знать последовательность запросов, будет послать и Мэри в Вашингтон, и Ноя в Балтимор, что потребует первоначального перемещения на 4850 миль без необходимости в последующих поездках. Уровень эффективности алгоритма составит 12100/4850, что примерно равно 2.5. Меняя параметры примера, уровень эффективности можно сделать как угодно большим.

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