Automatic summarization as a combinatorial optimization problem

Tsutomu Hirao, Jun Suzuki, Hideki Isozaki

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)


We derived the oracle summary with the highest ROUGE score that can be achieved by integrating sentence extraction with sentence compression from the reference abstract. The analysis results of the oracle revealed that summarization systems have to assign an appropriate compression rate for each sentence in the document. In accordance with this observation, this paper proposes a summarization method as a combinatorial optimization: selecting the set. of sentences that maximize the sum of the sentence scores from the pool which consists of the sentences with various compression rates, subject to length constrains. The score of the sentence is defined by its compression rate, content words and positional information. The parameters for the compression rates and positional information are optimized by minimizing the loss between score of oracles and that of candidates. The results obtained from TSC-2 corpus showed that our method outperformed the previous systems with statistical significance.

Original languageEnglish
Pages (from-to)223-231
Number of pages9
JournalTransactions of the Japanese Society for Artificial Intelligence
Issue number2
Publication statusPublished - 2009


  • Combinatorial optimization
  • Dynamic programming
  • Knapsack problem
  • Sentence compression
  • Text summarization


Dive into the research topics of 'Automatic summarization as a combinatorial optimization problem'. Together they form a unique fingerprint.

Cite this