There is a linear time algorithm for breaking text evenly into lines of maximum width. It uses SMAWK (or Knuth & Plass) and "evenly" means: http://en.wikipedia.org/wiki/Word_wrap#Minimum_raggedness
Is there an algorithm or a concave cost function for algorithm above which would take into account the number of lines I would like the text break into, instead of the maximum line width? Also in linear time?
In other words, I'm looking for a line breaking (or paragraph formation, or word wrapping) algorithm where the input is the desired number of lines, not the desired line width.
Just to describe a practically unusable approach: There are N words and N-1 spaces in-between each word pair, M is the desired number of lines (M <= N). After each space there might be at most one (possibly zero) line-break. Now, the algorithm would try to place the breaks in each possible combination, calculating the "raggedness" and return the best one. How to do it much faster?
Also, does such a problem have a name? What "family" of problems does it belong to? (E.g. "bin packing") If I wouldn't need the perfectly optimal solution, just a very good one, is it possible to solve it much faster? (some form of heuristics could be usable, if for a given input there were always the same, possibly sub-optimal, solution).
Chandra Chekuri suggested bellow "a problem in Kleinberg and Tardos chapter on dynamic programming". It was a good read but it deals with line breaking based on width rather than line count. It might be adaptable to this problem which is something I'm trying to figure out now. Here is a good link to the solution, they even claim to solve it in linear time: http://web.media.mit.edu/~dlanman/courses/cs157/HW5.pdf
Also, there is a chapter "8.5 The Partition Problem" in The Algorithm Design Manual by Skiena which seems to be exactly on-topic, I'm still reading it, tough. (Unfortunately, from what I understood it has quadratic time complexity)