Локальный поиск для задачи о k-медианах и задачи о размещении объектов: различия между версиями

Локальный поиск для задачи о k-медианах и задачи о размещении объектов (посмотреть исходный код)

85 байт добавлено , 27 апреля 2018

м

4446

правок

Версия от 11:18, 27 апреля 2018 (просмотреть исходный код) Irina (обсуждение \| вклад) (→‎Основные результаты) ← Предыдущая правка		Версия от 11:21, 27 апреля 2018 (просмотреть исходный код) Irina (обсуждение \| вклад) м (→‎Основные результаты) Следующая правка →
Строка 82:		Строка 82:


	Теорема 2 ([2]). Эвристика локального поиска, которая пытается добавить случайный центр i ~~… Ct~~ и удалить множество I(i), вычисляет 3 + "-аппроксимацию с высокой вероятностью за T = O(N log N(log N + 1/")) этапов улучшения, каждый из которых занимает O(N) времени.		'''Теорема 2 ([2]). Эвристика локального поиска, которая пытается добавить случайный центр <math>i \notin C_t \;</math> и удалить множество I(i), вычисляет <math>3 + \varepsilon \;</math>-аппроксимацию с высокой вероятностью за <math>T = O(N \; log \; N(log \; N + 1/ \varepsilon))</math> этапов улучшения, каждый из которых занимает O(N) времени.'''