A Study of Global Inference Algorithms in Multi-Document Summarization

The work in this paper studies the theoretical and empirical properties of various global inference algorithms for multi-document summarization. The paper starts by defining a general framework and proving that inference in it is NP-hard. It then presents three algorithms: The first is a greedy approximate method, the second a dynamic programming approach based on solutions to the knapsack problem, and the third is an exact algorithm that uses an Integer Linear Programming formulation of the problem. The paper empirically evaluates all three algorithms and shows that, relative to the exact solution, the dynamic programming algorithm provides near optimal results with preferable scaling properties.