An open problem

Pierre Fragniaud described a fun problem. Given G, its augmentation is to add a single (long range) edge to each vertex in G resulting in H. Now consider greedy routing on H where the shortest distances are given by G. The goal is to minimize the time for greedy routing. The authors in SPAA07 paper show an augmentation for arbitrary G such that the greedy routing time is roughly n^{1/3}. The best lower bound seems to be n^{1/\sqrt{\log n}.