I'm not totally sure, but I think the linear time papers I've read sacrifice some of the aspects of the original Knuth and Plass algorithm. I think some of those are going to be necessary to properly implement the Knuth and Plass algorithm in browser (also, floats are going to be interesting.)

The performance isn't actually that bad, I can perform line breaking in JavaScript on some very large documents, with the only performance bottleneck being DOM node creation (which native implementations won't suffer from.) If necessary the linebreaking could also be done incrementally, with a first first-fit pass and then the Knuth and Plass algorithm.

I could be mistaken, but I'm fairly certain Internet Explorer implements the Knuth and Plass algorithm when using `text-justify: newspaper`. Unfortunately, I can't check because it isn't open source. The output however is pretty much identical to what my JavaScript version generates, so I'm inclined to believe it is the Knuth and Plass algorithm.