Том 4, серия 1, номер 1, 1997 г., Стр. 79-87

УДК 519.854.3
Ю. В. Шамардин, А. В. Пяткин
О точности одного алгоритма разбиения множества

Аннотация:
Для решения задачи о разбиении $n$ целых положительных чисел на два подмножества с наиболее близкими суммами известен алгоритм загрузки предметов в ранец, который находит приближенное решение с относительной погрешностью не более 1/7, используя $O(n)$ шагов. В данной статье на основе частичного перебора разбиений и упомянутого выше алгоритма строится алгоритм $E_m, m=0,1, 2,\dots,$ который находит приближенное решение за $O(2^m{n})$ шагов. Доказывается, что максимальная относительная погрешность $\eta(E_m)$ этого алгоритма удовлетворяет неравенствам
$$ \frac{1}{7+3m}\leqslant\eta(E_m)\leqslant\frac{1}{6+2m} $$
Библиогр. 2.

Шамардин Ю. В. ¹
Пяткин А. В. ¹
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия

Статья поступила 3 декабря 1996 г.