Before revision:  Our (1 + \epsilon)-approximate algorithm runs in linear time when K\log( /(c_{low}\epsilon)) is O(N^C) for C < } 1  and c_{low} are upper and lower bounds on the optimal cost.
After revision:  Our (1 + \epsilon)-approximate algorithm runs in linear time when K\log( /(c_{low}\epsilon)) is O(N^C) for C < } 1 , where c_{high and c_{low} are upper and lower bounds on the optimal cost.