Some of the work on flexible computation has explored foundations of flexibility and value in basic algorithms such as sorting procedures. A partial sort is depicted by a set of points in a two dimensional represenation where one axis is the key of records and the other are the locations of the records. A diagonal line represents a completely sorted file. We can probe the value of partial results of computation by developing a utility model that captures alternate dimensions of value in the partial result. In the case of flexible sorting algorithms, we consider dimensions of value user's find in partial sorted files.
Utility models are typically functions of the user and context of application of the computation.
This figure highlights several dimensions of value in a partial sort that can be combined with a multiattribute utility model to generate an overall value of a partial result. Here is a graph of the utility of partial results with computation for Shellsort and Selection sort, generated by applying a specific utility model to the results of these sorting procedures. The utility model considers the contribution to the overall value of the result of several attributes of value. We show the performance over time of a two-opt approximation. In the context of a loss function, representing the cost of waiting for an increasingly better tour, we compute a net value, the curve appearing in the middle of the graph.