“The Concave Least-Weight Subsequence Problem Revisited”, Robert Wilber1998-09 (algorithms, T_eX; backlinks)⁠:

[uses Aggarwal et al 1987 in SMAWK] We are given an integer n and a real-valued function w(i, j) defined for integers 0 ≤ i < j ≤ n and with the property that w(i₀, j₀) + w(i₁, j₁) ≤ w(i₀, j₁) + w(i₁, j₀) for 0 ≤ i₀ < i₁ < j₀ < j₁ ≤ n. The concave least-weight subsequence problem is to find an integer k ≥ 1 and a sequence of integers 0 = l₀ < l₁ < … < l_{k − 1} < l_k = n such that Σ_{i = 0}^{k − 1} w(l_i, l_{i + 1}) is minimized. One application of this problem is determining optimal line breaks in a text formatting system.

Hirschberg & Larmore1987 showed that the concave least-weight subsequence problem can be solved in 𝒪(n log n) time and that if a certain extra condition is imposed it can be solved in 𝒪(n) time.

Here we show that the concave least weight subsequence problem can always be solved in 𝒪(n) time, without any extra conditions.

Backlinks: