Before revision:  For k=3, our algorithm runs in O(m^{ 21 }n) time, faster than the previous best algorithm, but gives a 4-approximate result.
After revision:  For k=3, our algorithm runs in O(m^{ 18 }n) time, faster than the previous best algorithm, but gives a 4-approximate result.