Paper: Computing Locally Coherent Discourses

ACL ID P04-1051
Title Computing Locally Coherent Discourses
Venue Annual Meeting of the Association of Computational Linguistics
Session Main Conference
Year 2004

We present the first algorithm that computes opti- mal orderings of sentences into a locally coherent discourse. The algorithm runs very efficiently on a variety of coherence measures from the literature. We also show that the discourse ordering problem is NP-complete and cannot be approximated.