No known \(O(1)\) -approximation algorithm can achieve the desirable time bounds in the open question.
The above references take \(m^{1+\Theta (1/k)}\)  preprocessing time to answer queries with a \(k\) -approximation in \(m^{o(1)}\)  time.
Meanwhile, the best conditional lower bound by Pătraşcu, Roditty, and Thorup [1]} only rules out a \((3-\varepsilon )\) -approximation with such time bounds under a set-intersection conjecture.Their conjecture and hardness result apply even for preprocessing algorithms with \(m^{1+o(1)}\)  space (and unbounded time), but higher lower bounds are not known even when restricting the time complexity.
Existing inapproximability results higher than the \(3-\varepsilon \)  barrier are either information-theoretic incompressibility arguments [2]}, [3]}, [4]} and therefore only rule out \(o(m)\)  space bounds, or in the cell-probe model [5]} and therefore only apply for query times up to \(\log {n}\) .The latter is due to the well-known barrier of proving higher unconditional lower bounds for any problem (see [6]}, [1]}). To prove inapproximability even with the more satisfying \(m^{o(1)}\)  restriction on the query time, we seem to need the conditional lower bounds approach of fine-grained complexity.
