Given document tree T, a summary preserves the original dependency relations if it forms a subtree rooted at r in T. Therefore, our aim is to find a rooted subtree of T that includes informative textual units.
for each v ∈ V , the length of v is denoted by v ≥ 0; for example, v is the number of words or characters in chunk v. If S ⊆ V is a subset of the textual units included in an obtained summary, its total length must be less than or equal to the given length limitation value L ≥ 0; namely, the following knapsack constraint must be satisfied: v∈S v ≤ L. The quality of summary S is evaluated by a monotone submodular function g. compressive summarization is formulated as STKP: At first glance, it may seem that the following naive greedy approach works well for this problem: Starting from root r, we sequentially add the most beneficial child to the current solution until the knapsack constraint is violated.