О сложности приближенных алгоритмов решения задачи целочисленного программирования

Для задачи целочисленного линейного программирования с булевыми переменными предложен $\varepsilon$-оптимальный алгоритм с полиномиальной по входу трудоёмкостью, где $\varepsilon$ не превосходит полинома от длины входа. Показано, что для задачи квадратичного булева программирования и любого полинома $\varepsilon(L)$ от длины входа проблема нахождения $\varepsilon(L)$-оптимального решения является $NP$-трудной.