The best known algorithms, say relabel-to-front, is O(m^1.5) and the paper proposes an algorithm which is O(m^(1+o(1)). Here, 1.5 is fixed but 1+o(1) can be anywhere between 1 and 2 based on your luck, and should be 1.5 on an average over variety of inputs. Still no free lunch.