It doesn’t really make sense in this case though, does it? One example is that Knapsack can be approximately solved in polynomial time for all tolerances eps (I

It doesn’t really make sense in this case though, does it? One example is that Knapsack can be approximately solved in polynomial time for all tolerances eps (I.e., it has a Fully-polynomial time approximation scheme, or FPTAS). The EMH is only talking about essentially approximate behavior (as the paper also mentions, with repeated experiments).