# Solving Multi-Document Summarization as an Orienteering Problem
## 5 The Proposed Solution
### Selecting Summary Sentences
#### 5.4.3. Correctness of the Reduction  
The correctness of the reduction of an MDS instance into an OP instance is presented and proved as follows.  
**Theorem 1**.: _Let \(MDS(D,L)\) be an MDS instance where \(D\) is a set of related documents to be summarized and \(L\) is the maximum summary length. Let \(OP(T_{max},V,A)\) be an OP instance where \(T_{max}\) represents its time budget, and \(V\) and \(A\) be the sets of vertices and arcs, respectively. An MDS instance has a solution summary \(S\) with a length up to \(L\) and its content coverage is maximized if and only if its corresponding OP instance given by Algorithm 1 has a solution path \(P\) that maximizes the total gained profit, while the total traveled time is less than or equal to \(T_{max}\)._  
Proof of Theorem 1.: Suppose that an MDS instance has a solution summary \(S\), which is a sequence of sentences \(\langle s_{s1},\ldots,s_{sq}\rangle\) where \(s_{sk}\) is a \(k^{th}\) sentence at \(S\) and \(q\) is the number summary sentences. The corresponding \(OP\) instance given by Algorithm 1 has a solution path \(p=\langle v_{1},v_{(s1)+1},\ldots,v_{(sq)+1},v_{N}\rangle\). Additionally, \(v_{(sk)+1}\) in \(P\) represents the \(k^{th}\) summary sentence (i.e., \(s_{sk}\)) of the corresponding \(MDS\) instance. Based on Algorithm 1, the profit of \(v_{(sk)+1}\) in \(P\) represents the coverage score of \(s_{sk}\) in \(S\). Moreover, the weight of the arc from, for example, vertex \(v_{sr}\) to vertex \(v_{sk}\) in \(P\), represents the added length by including \(s_{(sk)-1}\) in \(S\). Furthermore, time budget \(T_{max}\) represents summary length \(L\). Thus, the following can be concluded:  
* The length of \(S\) is less than or equal to \(L\), so the total traveled time of \(P\) is less than or equal to \(T_{max}\): \(\sum_{s_{i}\in S}l_{i}\leq L\Rightarrow\sum_{v_{i}\in P}\sum_{v_{j}\in P}t_{ ij}x_{ij}\leq T_{max}\) (time budget constraint).
* Maximizing the overall content coverage score of \(S\) will maximize the total gained profit of \(P\): \(max(\sum_{s_{i}\in S}cov_{i})\Rightarrow max(\sum_{v_{i}\in P}p_{i})\) (maximize the profit).  
Conversely, suppose that the OP instance has a solution path \(P\), which is a sequence of vertices \(\langle v_{1},v_{p2},\ldots,v_{py},v_{N}\rangle\), where \(pk\) represents the \(k^{th}\) vertex at \(P\) and \(y+1\) is the total number of visited vertices. Therefore, based on Algorithm 2, the corresponding MDS solution summary \(S=\langle s_{(p2)-1},\ldots,s_{(py)-1}\rangle\) is created by appending a sequence of sentences that are represented by the visited vertices in \(P\) starting from the second vertex until reaching the vertex located before the last one (i.e., ignoring the starting and the ending vertices). In other words, the \(k^{th}\) vertex in \(P\) represents the sentence \(s_{(pk)-1}\) in \(S\). As a result,  
* If the traveled time of \(P\) is less than or equal to \(T_{max}\), then the total length of \(S\) is less than or equal to \(L\): \(\sum_{v_{i}\in P}\sum_{v_{j}\in P}t_{ij}x_{ij}\leq T_{max}\Rightarrow\sum_{s_{ i}\in S}l_{i}\leq L\) (summary length).
* Maximizing the gained profit of \(P\) will maximize the score of the overall content coverage of \(S\): \(max(\sum_{v_{i}\in P}p_{i})\Rightarrow max(\sum_{s_{i}\in S}cov_{i})\) (maximize the coverage).