Before revision:  Our second algorithm gives a 1/(k(1+\epsilon))-approximation , is work-efficient, and has polylogarithmic span.
After revision:  Our second algorithm gives a 1/(k(1+\epsilon))-approximation and has polylogarithmic span.