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

Первый алгоритм с константным коэффициентом аппроксимации для k = 2 разработали Шмойс и др. [51], получив <math>\gamma = 3,16 \;</math>. Для k общего вида первый алгоритм с <math>\gamma = 3 \;</math> предложили Аардал, Чудак и Шмойс [1]. Для случая k = 2 Чжан [56] разработал алгоритм с коэффициентом аппроксимации 1,77. Он также показал, что для k = 3 и k = 4 задачу можно аппроксимировать в при <math>\gamma = 2,523 \;</math>* и <math>\gamma = 2,81 \;</math>, соответственно.