Задача о размещении объектов: различия между версиями

Первый алгоритм с константным коэффициентом аппроксимации в 1977 году разработали Корнюжо и др. [15] для задачи max-UFL. Они показали, что при открытии одного объекта за раз жадным образом, выбирая для открытия объект с самой высокой маржинальной прибылью, до тех пор, пока не останется объектов с положительной маржинальной прибылью, получается алгоритм с коэффициентом аппроксимации <math>(1 - 1/e) \approx 0,632 \;</math>. Лучший известный на сегодня коэффициент аппроксимации (0,828) получили Агеев и Свириденко [2].

Первый алгоритм с константным коэффициентом аппроксимации для задачи о k-медианах был разработан Чарикаром, Гухой, Тардош и Шмойсом [11]. Этот алгоритм LP-округления имеет коэффициент аппроксимации 6 2/3. Лучший известный на сегодня коэффициент аппроксимации, <math>3 + \epsilon \;</math>, при помощи эвристики локального поиска получили Арья и др. [6] (см. также отдельные разделы для метода k-медиан и задачи о размещении объектов).