Break text evenly into certain number of lines There is a linear time algorithm for breaking text evenly into lines of maximum width. It uses SMAWK (or Knuth &amp; 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 &lt;= 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).

Update

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)
If you can compute the raggedness of a line without knowing anything about the other lines, then you can model the problem as finding a minimum-weight $M$-link path in a graph. With concave integer weights for edges, there is an algorithm that solves the problem in $O(N \log U)$ time, where $U$ is the largest absolute edge weight. Another algorithm solves the problem in $N 2^{O(\sqrt{\log M \log \log N})}$ time for any concave edge weights, assuming $M = \Omega(\log N)$. Both algorithms assume that you can compute the weight of an edge in constant time.

You could also use binary search to find a line width such that SMAWK uses $M$ lines with it. In some cases, this algorithm does not guarantee a solution with exactly $M$ lines, however.