Before revision:  We also propose a simpler version of our (1 + \epsilon)-approximate algorithm which runs in a factor of \log(c_{ high }/(c_{ low }\epsilon)) from linear time, but is faster in practice.
After revision:  We also propose a simpler version of our (1 + \epsilon)-approximate algorithm which runs in a factor of \log(c_{ high }/(c_{ \text{low }\epsilon)) from linear time, but is faster in practice.