Снятие предположения об известном оптимальном радиусе

Вернемся к исходному вопросу: как выбрать хорошее множество из k центров, если оптимальный радиус покрытия неизвестен?

Стоит рассмотреть два разных ответа на этот вопрос. Во-первых, при разработке аппроксимирующих алгоритмов часто бывает концептуально полезно предположить, что значение, обеспечиваемое оптимальным решением, известно.

В таких ситуациях часто можно начать с алгоритма, спроектированного с учетом этого предположения, и преобразовать его в алгоритм, обеспечивающий сравнимые гарантии производительности простым перебором по диапазону «предположений» относительно оптимального значения.

В ходе выполнения алгоритма эта последовательность предположений становится все более и более точной, пока не будет достигнуто приближенное решение.

Для задачи о выборе центров это может происходить так: мы начинаем с очень слабых исходных предположений относительно радиуса оптимального решения: известно, что оно больше 0 и что оно не превышает максимального расстояния rmax между любыми двумя местами.

Итак, сначала мы делим разность между ними надвое и применяем разработанный выше жадный алгоритм со значением r = rmax/2.

Затем в соответствии со структурой алгоритма происходит одно из двух: либо мы находим множество из k центров с радиусом покрытия не более 2r, либо заключаем, что решения с радиусом покрытия не более r не существует.

В первом случае можно понизить оценку радиуса оптимального решения; во втором она должна быть повышена.

Так по радиусу проводится своего рода «бинарный поиск»: алгоритм итеративно определяет значения r0 < r1, чтобы мы знали, что оптимальный радиус больше r0, но решение имеет радиус не более 2r1.

По этим значениям описанный выше алгоритм выполняется с радиусом r = (r0 + r1)/2; затем мы либо решаем, что радиус оптимального решения больше r > r0, либо получаем решение с радиусом не более 2r = (r0 + r1) < 2r1. В любом случае оценка уточняется с одной или с другой стороны так же, как это происходит при бинарном поиске.

Алгоритм прекращает работу, когда оценки r0 и r1 оказываются достаточно близкими друг к другу; в этой точке наше решение с радиусом 2r1 близко к 2-аппроксимации оптимального радиуса, так как мы знаем, что оптимальное решение больше r0 (а следовательно, близко к r1).