4511
правок
Локальный поиск для задачи о k-медианах и задачи о размещении объектов: различия между версиями
Перейти к навигации
Перейти к поиску
Локальный поиск для задачи о k-медианах и задачи о размещении объектов (посмотреть исходный код)
Версия от 11:47, 19 апреля 2018
, 19 апреля 2018→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 46: | Строка 46: | ||
'''Задача о k-медианах''' | '''Задача о k-медианах''' | ||
Первую эвристику локального поиска с доказуемой гарантией эффективности предложили Арья и др. [1]. Это естественная эвристика с p заменами: пусть имеется текущее множество центров | |||
Первую эвристику локального поиска с доказуемой гарантией эффективности предложили Арья и др. [1]. Это естественная эвристика с p заменами: пусть имеется текущее множество центров <math>C_t \;</math> размера k; множество <math>\mathcal{E}_{t+1}</math> определяется следующим образом: | |||
где A | |||
<math>\mathcal{E}_{t+1} = \{ (C_t \backslash \mathcal{A}) \cup \mathcal{B}</math>, где <math>\mathcal{A} \subseteq C_t, \mathcal{B} \subseteq \mathcal{F} \backslash C_t, |\mathcal{A}| = |\mathcal{B}| \le p \}</math>. | |||
| Строка 81: | Строка 82: | ||
'''Варианты с ограничением пропускной способности''' | '''Варианты с ограничением пропускной способности''' | ||
Эвристики локального поиска также называются вариантами задач о k-медианах и о размещении объектов с ограничением пропускной способности. В этом варианте каждый возможный объект i 2 F может обслуживать не более ui пользователей. В случае мягкого варианта задачи о размещении объектов с ограничением пропускной способности ri _ 0 можно открыть в i 2 F, так что стоимость объекта составит fi ri, а количество обслуживаемых пользователей – не более riui . Задача оптимизации заключается в выборе значения ri для каждого i 2 F таким образом, чтобы назначение пользователей центрам удовлетворяло ограничению на пропускную способность каждого центра, а стоимость открытия центров и назначения пользователей была минимальной. Для этого варианта Арья и др. [1] предложили эвристику локального поиска, обеспечивающую разрыв локальности 4 + ". | Эвристики локального поиска также называются вариантами задач о k-медианах и о размещении объектов с ограничением пропускной способности. В этом варианте каждый возможный объект i 2 F может обслуживать не более ui пользователей. В случае мягкого варианта задачи о размещении объектов с ограничением пропускной способности ri _ 0 можно открыть в i 2 F, так что стоимость объекта составит fi ri, а количество обслуживаемых пользователей – не более riui . Задача оптимизации заключается в выборе значения ri для каждого i 2 F таким образом, чтобы назначение пользователей центрам удовлетворяло ограничению на пропускную способность каждого центра, а стоимость открытия центров и назначения пользователей была минимальной. Для этого варианта Арья и др. [1] предложили эвристику локального поиска, обеспечивающую разрыв локальности 4 + ". | ||
| Строка 88: | Строка 90: | ||
'''Родственные алгоритмические техники''' | '''Родственные алгоритмические техники''' | ||
Задачи о k-медианах и задачи о размещении объектов могут похвастаться долгой историей аппроксимации с достойными результатами. Начиная с первого исследования задачи о размещении объектов без ограничений на пропускную способность, выполненного Корнюжо, Немхаузером и Уолси [5], которые представили естественную релаксацию линейного программирования (LP) для этой задачи, было разработано несколько аппроксимаций с константными коэффициентами, использующих различные техники – таких как округление LP-решения [11, 15], локальный поиск [2, 9], прямо-двойственная схема [7] и двойное выравнивание [6]. Для задачи о k-медианах первая аппроксимация с константным коэффициентом 62 3 [3] была получена в результате округления естественной LP-релаксации при помощи обобщения техники фильтрации, предложенной в работе [11]. Результат был последовательно улучшен до 4-аппроксимации при помощи лагранжевой релаксации и прямо-двойственной схемы [2, 7], а затем до (3 + ")-аппроксимации при помощи локального поиска [1]. | Задачи о k-медианах и задачи о размещении объектов могут похвастаться долгой историей аппроксимации с достойными результатами. Начиная с первого исследования задачи о размещении объектов без ограничений на пропускную способность, выполненного Корнюжо, Немхаузером и Уолси [5], которые представили естественную релаксацию линейного программирования (LP) для этой задачи, было разработано несколько аппроксимаций с константными коэффициентами, использующих различные техники – таких как округление LP-решения [11, 15], локальный поиск [2, 9], прямо-двойственная схема [7] и двойное выравнивание [6]. Для задачи о k-медианах первая аппроксимация с константным коэффициентом 62 3 [3] была получена в результате округления естественной LP-релаксации при помощи обобщения техники фильтрации, предложенной в работе [11]. Результат был последовательно улучшен до 4-аппроксимации при помощи лагранжевой релаксации и прямо-двойственной схемы [2, 7], а затем до (3 + ")-аппроксимации при помощи локального поиска [1]. | ||