The Karger-Stein algorithm is optimal for k-cut.

Anupam Gupta, Euiwoong Lee, Jason Li

Browse the full STOC paper archive.