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