 Line breaking with squared slack cost

Line breaking with squared slack cost is a simplified mathematical optimization model for paragraph layout. Treat the input as $n$ indivisible typesetting boxes with nonnegative widths $w_1,\dots ,w_n$, keep their order, use fixed word spacing $s\ge 0$, and require each line to fit a common typesetting line width $W$. This model isolates the choice of breaks from adjustable spacing and hyphenation.

Let $P_j={\sum }_{k=1}^j{w}_k$ be the prefix sum, with $P_0=0$. Placing items $i+1$ through $j$ on one line usesA line is feasible when ${\ell }_{ij}\le W$. Charge $(W-{\ell }_{ij}{)}^2$ for a nonfinal line and zero for the final line. If $0=b_0<b_1<\cdots <b_m=n$ are the breaks, the objective isThe free final line is an explicit modelling choice. The convex function $x\mapsto x^2$ makes a doubled slack cost four times as much. For two slacks with fixed total,so greater imbalance increases their sum of squares. Actual break choices can also alter the line count and total slack; the whole paragraph still needs to be optimized.

Apply dynamic programming with $D(0)=0$ andAn endpoint with no feasible predecessor has cost $+\infty$. The same recurrence finds a shortest path through the directed acyclic graph of feasible line choices. The principle of optimality explains the recurrence. Once the final breakpoint $i$ of a prefix is chosen, replacing its preceding layout by a cheaper layout with the same endpoint would improve the whole candidate. Conversely, each feasible predecessor and final line produces a valid candidate. Induction over $j$ therefore gives the optimum. Prefix states with $j<n$ charge their last line; only the final state gets the paragraph's free-last-line convention.

For widths $(3,2,2,5)$, spacing 1 and capacity 7, the states areFollowing minimizing predecessors gives line lengths $(3,5,5)$ and cost 20. The line breaking diagram compares this with the cost 26 of greedy line breaking. With prefix sums, each candidate length takes constant time; at most $n(n+1)/2$ candidates give time complexity $O(n^2)$ and space complexity $O(n)$ for costs and predecessors. The big O notation describes this fixed-space model; the Knuth-Plass line-breaking algorithm includes additional typography-specific choices.