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

Нерешённые проблемы информатики: Существует ли k-эффективный алгоритм для решения задачи 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)

Пример

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

Представим алгоритм для назначения исполнителей запросам, который всегда назначает ближайшего исполнителя для обработки поступившего запроса. Предположим также, что каждое утро рабочего дня клиенту в Вашингтоне нужна помощь, в то время как пополудни каждого дня помощь ожидает клиент в Балтиморе. Клиент в Сан-Франциско никогда помощь не запрашивает. Тогда наш алгоритм будет назначать одного исполнителя, скажем, Мэри, в Вашингтон, после чего она всегда будет ближайшим исполнителем к очередному запросу. Таким образом, каждый день наш алгоритм повлечёт расходы переезда от Вашингтона до Балтимора и обратно, 110 км. После года работы алгоритма потребуется проехать 33000 км — 4800 км нужно проехать, чтобы добраться с западного побережья, и 29200 км нужно проехать, чтобы поочерёдно обслуживать клиентов в Вашингтоне и Балтиморе. С другой стороны, оптимальной стратегией, если знать последовательность запросов, будет послать и Мэри в Вашингтон, а Ноя в Балтимор, что потребует первоначального перемещения на 9700 км, но последующие поездки будут не нужны. Уровень эффективности алгоритма составит 33000/9700, что примерно равно 3.4. Меняя параметры примера, уровень эффективности можно сделать как угодно большим.

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