Жадные алгоритмы для задачи о ранце: поведение в среднем

Изучается поведение в среднем известных “жадных” методов для одномерной задачи о ранце при стремлении числа переменных $n$ к бесконечности. Предполагается, что правая часть ограничения $b$ линейно зависит от $n$, т.е. $b=\lambda n$. Показано, что при $\lambda>1/2-t/3$ прямой и двойственный жадные методы имеют асимптотическую погрешность $t$.