Cole's improvement to the sorting-based parametric search technique provides an automatic way of saving a logarithmic factor in the running time of an optimization problem over that achievable using the standard parametric search method. Unfortunately, this improvement comes at the expense of making an already complicated algorithm even more complex; hence, his technique has been mostly of theoretical interest. In this paper, we show that the same asymptotic complexity can be achieved in a way that is both simple and practical (i.e., suitable for actual implementation).
Joint work with Michael Goodrich.