4511
правок
Локальный поиск для задачи о k-медианах и задачи о размещении объектов: различия между версиями
Перейти к навигации
Перейти к поиску
м
Локальный поиск для задачи о k-медианах и задачи о размещении объектов (посмотреть исходный код)
Версия от 11:05, 27 апреля 2018
, 27 апреля 2018→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 71: | Строка 71: | ||
Очевидно, | | Очевидно, <math>|\mathcal{E}_{t + 1}| = O(m^2)</math>, что делает время выполнения полиномиальным от размера входных данных и значения <math>1/ \varepsilon \;</math>. Коруполу, Плакстон и Раджамаран [9] показали, что эта эвристика обеспечивает разрыв локальности не более <math>5 + \varepsilon \;</math>. Арья и др. [1] выполнили более строгий анализ, показав, что эвристика достигает разрыва локальности <math>3 + \varepsilon \;</math> и что эта граница является точной в том смысле, что существуют экземпляры задачи, для которых разрыв локальности строго равен 3. | ||
Эвристика «''добавить один, удалить несколько''», предложенная Чарикаром и Гухой [2], несколько сложнее. Она добавляет один объект и отбрасывает все объекты, которые становятся несущественными в новом решении. | |||
<math>\mathcal{E}_{t + 1} = \{(C_t \cup \{ i \} ) \backslash I(i),</math> где <math>i \in \mathcal{F} \backslash C_t, I(i) \subseteq C_t \}.</math> | |||
Множество 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] сформулировали следующую теорему. | Множество 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] сформулировали следующую теорему. | ||