Before revision:  Our first algorithm gives a 1/k-approximation and is based on iteratively peeling vertices with the lowest clique counts; our algorithm is work-efficient, but we prove that this process is P-complete and hence does not have polylogarithmic span. Our second algorithm gives a 1/(k(1+\epsilon))-approximation , is work-efficient, and has polylogarithmic span.
After revision:  Our first algorithm gives a 1/k-approximation and the second of which is a 1/(k(1+\epsilon))-approximation , is work-efficient, and has polylogarithmic span.