Локальный поиск для задачи о k-медианах и задачи о размещении объектов: различия между версиями
Перейти к навигации
Перейти к поиску
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 46: | Строка 46: | ||
'''Задача о k-медианах''' | '''Задача о k-медианах''' | ||
Первую эвристику локального поиска с доказуемой гарантией эффективности предложили Арья и др. [1]. Это естественная эвристика с p заменами: пусть имеется текущее множество центров Ct размера k; множество Et+1 определяется следующим образом: | |||
Et+1 =f(Ct nA) [ B ; | |||
где A Ct ;B F n Ct ; jAj = jBj _ pg : | |||
Вышеописанное обозначает простую замену не более чем p центров из Ct тем же количеством центров из F n Ct. Вспомним, что |D| = n и |F| = m. Очевидно, |Et+1| _ (k(m _ k))p _ (km)p. Начальное множество C0 выбирается произвольным образом. Значение p является параметром, от которого зависят время выполнения и коэффициент аппроксимации. Он выбирается константным, так что |Et| является полиномом от m. | |||
Теорема 1 ([1]). Эвристика с p заменами обеспечивает разрыв локальности (3 + 2/p) + ", а время выполнения составляет O(nk(log(nD))/"(mk)p). Кроме того, для любого значения p существует экземпляр задачи о k-медианах, в которой эвристика с p заменами обеспечивает разрыв локальности, в точности равный (3 + 2/p). | |||
Положив p = 1/", получим, что вышеописанная эвристика имеет коэффициент аппроксимации 3 + " и время выполнения ˜O(n(mk)O(1/")). | |||
'''Задача о размещении объектов''' | |||
Поскольку в этой задаче уже нет ограничения на количество центров, этап локального улучшения требует соответствующей модификации. Были разработаны две эвристики локального поиска, обеспечивающие разрыв локальности 3 + " за полиномиальное время. | |||
Эвристика «добавление, удаление и замен», предложенная Кюном и Хамбургером [10], добавляет центр в Ct, исключает центр из Ct, либо заменяет центр из Ct центром из F n Ct. Начальное множество C0 также выбирается произвольно. | |||
Et+1 = f(Ct nA) [ B; где A jAj = 0; jBj = 1 или jAj = 1; jBj = 0; или jAj = 1; jBj = 1g | |||
Очевидно, |Et+1| = O(m2), что делает время выполнения полиномиальным от размера входных данных и значения 1/". Коруполу, Плакстон и Раджамаран [9] показали, что эта эвристика обеспечивает разрыв локальности не более 5 + ". Арья и др. [1] выполнили более строгий анализ, показав, что эвристика достигает разрыва локальности 3 + " и что эта граница является точной в том смысле, что существуют экземпляры задачи, для которых разрыв локальности строго равен 3. | |||
Эвристика «добавить один, удалить несколько», предложенная Чарикаром и Гухой [2], несколько сложнее. Она добавляет один объект и отбрасывает все объекты, которые становятся несущественными в новом решении. | |||
Et+1 = f(Ct [ fig) n I(i); где i 2 F n Ct ; I(i) | |||
Множество I(i) вычисляется следующим образом. Обозначим за W множество элементов, расположенных ближе к i, чем к назначенным им центрам в Ct. При вычислении I(i) этими элементами можно пренебречь. Для каждого центра s 2 Ct обозначим за Us все элементы, назначенные s. Если fs +Pj2UsnW djd( j; s) > Pj2UsnW djd( j; i), то дешевле удалить объект s и переназначить элементы из Us n W элементу i. В этом случае s размещается в I(i). Обозначим N = m + n. Таким образом, процедура вычисления I(i) требует O(N) времени, что делает общее время выполнения полиномиальным. Чарикар и Гуха [2] сформулировали следующую теорему. | |||
Теорема 2 ([2]). Эвристика локального поиска, которая пытается добавить случайный центр i … Ct и удалить множество I(i), вычисляет 3 + "-аппроксимацию с высокой вероятностью за T = O(N log N(log N + 1/")) этапов улучшения, каждый из которых занимает O(N) времени. | |||
'''Варианты с ограничением пропускной способности''' | |||
Эвристики локального поиска также называются вариантами задач о k-медианах и о размещении объектов с ограничением пропускной способности. В этом варианте каждый возможный объект i 2 F может обслуживать не более ui пользователей. В случае мягкого варианта задачи о размещении объектов с ограничением пропускной способности ri _ 0 можно открыть в i 2 F, так что стоимость объекта составит fi ri, а количество обслуживаемых пользователей – не более riui . Задача оптимизации заключается в выборе значения ri для каждого i 2 F таким образом, чтобы назначение пользователей центрам удовлетворяло ограничению на пропускную способность каждого центра, а стоимость открытия центров и назначения пользователей была минимальной. Для этого варианта Арья и др. [1] предложили эвристику локального поиска, обеспечивающую разрыв локальности 4 + ". | |||
В жесткой версии задачи о размещении объектов с ограничением пропускной способности у объекта i 2 F имеется строгая граница ui количества объектов, которые могут быть ему назначены. Если пропускная способность ui всех объектов одинакова (однородный случай), Коруполу, Плакстон и Раджамаран [9] представили изящную эвристику локального поиска, основанную на решении задачи о перевозках с промежуточными пунктами и обеспечивающую разрыв локальности 8+". Чудак и Уильямсон [4] улучшили анализ этой эвристики, показав, что разрыв локальности составляет 6 + ". В случае неоднородной пропускной способности требуется кардинально иной подход; Пал, Тардош и Уэкслер [14] представили эвристику локального поиска на базе сетевого потока, обеспечивающую разрыв локальности 9 + ". Махдиан и Пал [12] улучшили эту границу до 8 + " за счет обобщения нескольких техник локального поиска, описанных выше, для получения константного коэффициента аппроксимации для варианта задачи о размещении объектов, в которой стоимости объектов являются произвольными неубывающими функциями от потребностей обслуживаемых ими пользователей. | |||
'''Родственные алгоритмические техники''' | |||
Задачи о k-медианах и задачи о размещении объектов могут похвастаться долгой историей аппроксимации с достойными результатами. Начиная с первого исследования задачи о размещении объектов без ограничений на пропускную способность, выполненного Корнюжо, Немхаузером и Уолси [5], которые представили естественную релаксацию линейного программирования (LP) для этой задачи, было разработано несколько аппроксимаций с константными коэффициентами, использующих различные техники – таких как округление LP-решения [11, 15], локальный поиск [2, 9], прямо-двойственная схема [7] и двойное выравнивание [6]. Для задачи о k-медианах первая аппроксимация с константным коэффициентом 62 3 [3] была получена в результате округления естественной LP-релаксации при помощи обобщения техники фильтрации, предложенной в работе [11]. Результат был последовательно улучшен до 4-аппроксимации при помощи лагранжевой релаксации и прямо-двойственной схемы [2, 7], а затем до (3 + ")-аппроксимации при помощи локального поиска [1]. | |||
== Применение == | |||
Задача о размещении объектов многократно изучалась в работах, посвященных исследованию операций [5, 10]; она является базовым примитивом для нескольких задач о местонахождении ресурсов. Метрики k-медиан и k-средних широко применяются в кластеризации или обучении без учителя. Для алгоритмов кластеризации было предложено несколько улучшений эвристик по отношению к базовой схеме локального поиска: метод k-медоидов [8] выбирает случайную входную точку и заменяет ее одним из существующих центров, если такая замена приводит к улучшению; реализация CLARA [8] метода k-медоидов выбирает центры из случайной выборки входных точек для ускорения вычисления; эвристика CLARANS [13] осуществляет новую случайную выборку подходящих центров перед каждым этапом улучшения, что еще больше повышает эффективность алгоритма. | |||
== См. также == | |||
* [[Задача о размещении объектов]] | |||
== Литература == | |||
1. Arya, V., Garg, N., Khandekar, R., Meyerson, A., Munagala, K., Pandit, V.: Local search heuristics for k-median and facility location problems. SIAM J. Comput. 33(3), 544–562 (2004) | |||
2. Charikar, M., Guha, S.: Improved combinatorial algorithms for facility location problems. SIAM J. Comput. 34(4), 803–824 (2005) | |||
3. Charikar, M., Guha, S., Tardos, É., Shmoys, D.B.: A constant-factor approximation algorithmfor the k-median problem(extended abstract). In: STOC ’99: Proceedings of the thirty-first annual ACMsymposium on Theory of computing, pp. 1–10. Atlanta, May 1-4 1999 | |||
4. Chudak, F.A., Williamson, D.P.: Improved approximation algorithms for capacitated facility location problems. Math. Program. 102(2), 207–222 (2005) | |||
5. Cornuejols, G., Nemhauser, G.L., Wolsey, L.A.: The uncapacitated facility location problem. In: Discrete Location Theory, pp. 119–171. Wiley, New York (1990) | |||
6. Jain, K., Mahdian, M., Markakis, E., Saberi, A., Vazirani, V.V.: Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP. J. ACM50(6), 795–824 (2003) | |||
7. Jain, K., Vazirani, V.V.: Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and lagrangian relaxation. J. ACM 48(2), 274–296 (2001) | |||
8. Kaufman, L., Rousseeuw, P.J.: FindingGroups inData: An Introduction to Cluster Analysis.Wiley, New York (1990) | |||
9. Korupolu, M.R., Plaxton, C.G., Rajaraman, R.: Analysis of a local search heuristic for facility location problems. In: SODA ’98: Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, pp. 1–10. San Francisco, USA; 25–26 January 1998 | |||
10. Kuehn, A.A., Hamburger, M.J.: A heuristic program for locating warehouses. Management Sci. 9(4), 643–666 (1963) | |||
11. Lin, J.-H., Vitter, J.S.: "-approximations with minimum packing constraint violation (extended abstract). In: STOC ’92: Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, pp. 771–782. Victoria (1992) | |||
12. Mahdian, M., Pál, M.: Universal facility location. In: European Symposium on Algorithms, pp. 409–421. Budapest, Hungary, September 16–19 2003 | |||
13. Ng, R.T., Han, J.: Efficient and effective clustering methods for spatial data mining. In: Proc. Symp. on Very Large Data Bases (VLDB), pp. 144–155. Santiago de Chile, 12–15 September 1994 | |||
14. Pál, M., Tardos, É., Wexler, T.: Facility location with nonuniform hard capacities. In: Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, pp. 329–338. Las Vegas, 14–17 October 2001 | |||
15. Shmoys, D.B., Tardos, É., and Aardal, K.: Approximation algorithms for facility location problems. In: Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, pp. 265–274. El Paso, 4–6 May 1997 | |||