Асимптотические гарантированные оценки точности

Алгоритм	T*A
NF	O (n)	2.000	2.000	1.500	1.333
FF	O (n log n)	1.700	1.500	1.333	1.250
BF	O (n log n)	1.700	1.500	1.333	1.250
NFD	O (n log n)	1.691	1.424	1.302	1.234
FFD	O (n log n)	1.222	1.183	1.183	1.150
BFD	O (n log n)	1.222	1.183	1.183	1.150

— асимптотическая точность для примеров с весами предметов
w_i £ a, для всех i Î L.

Теорема. Для любого e Î (0,1] существует алгоритм A_e, который находит упаковку с числом контейнеров не более (1 + 2 e) OPT + 1. Трудоемкость A_e полиномиально зависит от n.

(Без доказательства)

Алгоритм A_e

1. Удалить предметы с весом менее e.

2. Упорядочить оставшиеся предметы и разбить их на K = é1/ e ²ù групп.

3. В каждой группе увеличить веса предметов до максимального веса в группе.

4. Найти оптимальную упаковку предметов, имеющих только K различных весов каждый из которых не менее e.

5. Вернуть исходные веса предметов и применить алгоритм FF для
предметов с весом менее e.