Patent Document ID: 20070260449
Application ID: 11415196
Patent Status: 0

Claim One:
1. A computer-implemented optimization method for instance-based sentence boundary determination comprising the steps of setting an initial upper bound (UB) of a cost associated with an optimized solution to a lowest cost derived by several greedy algorithms; identifying all corpus instances stored in an electronic database that contains one or more of a plurality of desired propositions; forming a search tree structure with branches for each of plurality of identified corpus instances that contain one or more of said plurality of desired propositions; deleting one or more of a plurality of undesired propositions from said identified corpus instances; updating an overall cost with one or more deletion costs; inserting one or more of said plurality of desired propositions that were not contained in said corpus instance into said corpus instance; updating the overall cost with one or more insertion costs; calculating a lower bound (LB) of a cost associated with a current solution or partial solution; pruning a current search branch if the LB is greater than the UB; recursively computing a best solution associated with generating one or more additional sentences to convey the rest of said plurality of desired propositions that were not contained in said corpus instance; updating the overall cost with a boundary cost plus a cost associated with the best solution found by the recursively computing procedure; updating UB if the current overall cost is lower than UB; and outputting a solution that has the lowest overall cost using a set of said identified corpus instances with a set of said deletion, insertion and sentence break operations.