4) Solve the Optimization Problem

[hkuhn]

Summary Generation Sub-Tasks in-order

Solve the optimization problem. This is the fourth and final step in summary generation.

Classical knapsack problem in dynamic programming

f_k (lambda_k) = max{mu_k In_k + f_{k-1} (lambda_{k-1}}
lambda_k = lambda_{k+1} - mu_{k+1} l_{k+1}
K = t, 1 <= t <= T
lambda_0 = 0
lambda_T = N_s
f_0 (lambda_0) = 0

f_k (lambda_k) = max of summary importance in stage k
K = stage variable to describe current sentence
lambda_k = remaining length before K starts
mu_k = decision variable for sentence