16

The pagination problem as posed by Donald Knuth and Michael Plasss is an NP-complete problem. At an intuitive level, this problem is related to the packing problem, so quite difficult to solve. However, by relaxing L2 metric to L1, Brüggemann-Klein et al. [1] have claimed to have solved it. Since I am not an expert at judging this, I would like to know if this problem has really been solved, at least in the L1 metric.


[1] Brüggemann-Klein, Anne, Rolf Klein, and Stefan Wohlfeil. "On the pagination of complex documents." Computer Science in Perspective. Springer Berlin Heidelberg, 2003. 49-68.

  • 3
    interesting, related, but off-topic. better to ask on CS.SE perhaps? I did some research into the problem for my thesis – I can't find the original source, but the problem has been solved with Pareto-optimality. – Sean Allred Feb 28 '15 at 18:31
  • Ah, goodness me, I linked to it! See the last link in the question body: tex.stackexchange.com/q/128454/17423 and a related slidedeck – Sean Allred Feb 28 '15 at 18:35
  • @DavidCarlisle Fixed :) For reference, this is the page I am talking about: bowman.infotech.monash.edu.au/~pmoulder/line-breaking/… – Sean Allred Feb 28 '15 at 18:44
  • Thanks Sean and David! This looks too good for Alex Holkner's Honors thesis. Instead of a single parameter, as in Knuth-Plass, they are going for optimising on multiple parameters at the same time; quite clever. I suppose they will go for machine learning with training sets, feedback loops etc. eventually ;) – Sukii Mar 3 '15 at 5:01
  • 1
    I checked many typesetting systems, Word, 3B2, InDesign, Browsers etc. Most of them don't allow back-propagation of H&J effects (InDesign has some minor back-propagation), in order to be fast, so they are sub-optimal. You need that for WYSIWYG systems. So I doubt if there are any improvements made by commercial typesetting systems on the TeX algorithm, in terms of quality, but it will be interesting to hear from them if there is anything new at all. – Sukii Mar 3 '15 at 5:15
12

What Plass proved in his PhD thesis was that paginating documents using dynamic programming with very specific functions for optimisation are NP complete but also that for other functions this is not the case. Nevertheless Knuth felt that there isn't any method (i.e., a reasonable goal function to minimize) that would both work in practice with the computer power at hand and at the same time would provide reasonable results. Thus TeX ended up using a simple first-fit algorithm for page breaking.

Basically we have to remind ourselves that there is no such thing as solving "the line breaking problem" or solving the "page breaking problem". It depends all on what criteria you add into your algorithm and what kind of functions you look at that should get optimized (i.e., that define your "quality") and each combination of those result in quite a different problem being solved. Knuth's linebreaking algorithm, for example, is only optimal with respect to the goal function it minimizes (which for most practical situations provides a useful definition of quality), but clearly it has no idea of rivers in a paragraph and will happily produce them. The demerits he is minimizing are carefully restricted so that you don't need to keep track how you reached a certain breakpoint (other than knowing whether the previous line was loosely or tightly set but not what happened earlier). River processing would throw that off guard and probably make the linebreaking problem NP complete.

Wohlfeil in his PhD (and the paper with Anne you cite is an earlier version of this work) looks at the following problem:

  • the document model consists of text and figures
  • figures can float but will preserve order
  • they will not appear before their main reference (or are at least visible from there, i.e., they may float slightly in front of the main reference)
  • the quality function is based on looking at how many pages one has to turn to see a figure from its main reference

(there are a few other variations and extensions like footnotes, or double spreads that may be larger than others but the above is the gist of the page model considered)

For that he has "solved" the pagination problem, the question is however if that is in practical terms sufficient to be used in real life production. In his PhD he documents a prototype implementation called X-Formatter, but that system never appeared in the wild (as far as I know).

In my opinion it is not a generally usable solution (though a clear step towards such a system) as it doesn't cover, for example:

  • use of more complex layouts with more than one column
  • more than a single figure stream where different types of floats can surpass each other while competing for space.

I do think, however, that he has clearly shown that there are goal functions that are measuring "quality" in a useful practical way that are usable with a dynamic programming approach and given todays computers could perhaps be generalized to provide a system the results useful paginations in acceptable time.

1

Here is a link to the document suggested by Sean Allred: Global multiple objective line breaking

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.