= Line breaking with squared slack cost
{title2=$\min\sum_{k=1}^{m-1}(W-\ell_k)^2$}
\b[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,\ldots,w_n$, keep their order, use fixed <word spacing> $s\geq0$, 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 uses
$$
\ell_{ij}=P_j-P_i+(j-i-1)s.
$$
A line is feasible when $\ell_{ij}\leq 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 is
$$
\boxed{\min_{\text{feasible breaks}}
\sum_{k=1}^{m-1}(W-\ell_{b_{k-1},b_k})^2.}
$$
The 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,
$$
a^2+b^2=\frac{(a+b)^2+(a-b)^2}{2},
$$
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$ and
$$
D(j)=\min_{\substack{0\leq i<j\\\ell_{ij}\leq W}}
\bigl(D(i)+c(i,j)\bigr),\qquad
c(i,j)=\begin{cases}(W-\ell_{ij})^2&j<n,\\0&j=n.\end{cases}
$$
An 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 are
$$
\boxed{(D(0),D(1),D(2),D(3),D(4))=(0,16,1,20,20).}
$$
Following 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.
Back to article page
