Быстрый алгоритм решения квадратичной задачи о ранце

В работе рассматривается задача квадратичного программирования со строго выпуклой сепарабельной целевой функцией, единственным линейным ограничением и двусторонними ограничениями на переменные. В англоязычной литературе эта задача называется Convex Knapsack Separable Quadratic Problem, или сокращенно - CKSQP. Нас интересует алгоритм решения задачи CKSQP с линейной сложностью. Посвященные этой теме работы содержат неточности в описании алгоритмов и неэффективные реализации. В данной работе удалось преодолеть имеющиеся трудности.