There is also a paper that claims linear time for formatting paragraphs using dynamic programming: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.47.32

There is also a paper that claims linear time for formatting paragraphs using dynamic programming: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.47.3229 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.47.3... I haven't really wrapped my head around the paper yet, but I think it only holds if you take out some of the elements of the original Knuth & Plass algorithm (the box, glue and penalty model.) Nevertheless, linear time seems possible for a total-fit algorithm if you're willing to give up that model. There is also a Haskell and C++ implementation (with source code) available on the authors web page: http://progtools.comlab.ox.ac.uk/members/oege/publications/scp99 http://progtools.comlab.ox.ac.uk/members/oege/publications/s...