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

Были рассмотрены два варианта задачи о размещении объектов с мягкими ограничениями на пропускную способность. Оба предполагают равную пропускную способность, т. е. <math>u_i = u \;</math> для всех <math>i \in \mathcal{F}</math>. В первом варианте решение является «допустимым», если y-переменные либо принимают значение 0, либо имеют значение между 1 и <math>\gamma' \ge 1 \;</math>. Заметим, что <math>\gamma' \;</math> не обязательно должно быть целым, так что построенное решение не обязательно является целочисленным. Это можно интерпретировать так, что каждому объекту i дозволяется расширяться, обеспечивая пропускную способность <math>\gamma' u \;</math> со стоимостью <math>\gamma' f_i \;</math>. Алгоритм <math>(\gamma, \gamma') \;</math>-аппроксимации представляет собой полиномиальный алгоритм, приводящий к такому допустимому решению, общая стоимость которого не более чем в <math>\gamma \;</math> раз превышает истинную оптимальную стоимость, имеющую место в случае <math>y \in \{0, 1 \}^{n_f} \;</math>. Шмойс и др. разработали алгоритм (5,69< 4,24)-аппроксимации для варианта этой задачи с возможностью разделения и алгоритм (7,62< 4,29)-аппроксимации для варианта без возможности разделения.