

![0_image_0.png](0_image_0.png) 
between the nodes Thi and Thj is Ci,j **. The orderings from the input articles provide us**
directly with a preference function and, therefore, we do not need to learn it.

Unfortunately this problem is NP-complete; Cohen et al. (1999) prove it by reducing from CYCLIC-ORDERING (Galil & Megido, 1977). However, using a modified version of topological sort provides us with an approximate solution. For each node, we assign a weight equal to the sum of the weights of its outgoing edges minus the sum of the weights of its incoming edges. We first pick up the node with maximum weight, ordering it ahead of the other nodes, delete it and its outgoing edges from the precedence graph and update properly the weights of the remaining nodes in the graph. We then iterate through the nodes until the graph is empty. Cohen et al. (1999) show that this algorithm produces a tight approximation of the optimal solution. Currently MultiGen **uses an implementation**
of this algorithm for its ordering component.

Figures 4 and 5 show examples of produced summaries. One feature of this strategy is that it can produce several orderings with the same weight. This happens when there is a tie between two opposite orderings. In this situation, this **strategy does not provide enough** constraints to determine one optimal ordering; an ordering **is chosen randomly among the** orders with maximal weight.

## 4.1.2 Evaluation

We asked three human judges (not including ourselves) to classify the quality of the order of information in 25 summaries produced using the MO algorithm into three categories— Poor, Fair and Good. We use an operational definition of a Poor **summary as a text whose**