$(1-\hat{I}\mu )$-Approximation of Knapsack in Nearly Quadratic Time

Xiao Mao

Knapsack is one of the most fundamental problems in theoretical computer science. In the $(1-\hat{I}\mu )$-approximation setting, although there is a fine-grained lower bound of $(n + 1 /…