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