Sorting and selection with structured costs

The (unit-cost) comparison treemodel has long been the basis of evaluating the performance of algorithms for fundamental problems like sorting and searching. In this model, the as-sumption is that elements of some total order are not given to us directly, but only through a black-box, which performs comparisons between the elements and outputs the result of the comparison. While the comparison tree model has served us well, the recent interest in the concept of priced information [9, 10] encourages us to look more closely at this model. The study of the effect of priced information on basic algorithmic problems was initiated by the paper of Charikar et al. [5]. In this paper, we continue the study of sorting and selection in the priced comparison model, i.e., when comparison has an associated cost and answer some of the open problems suggested by [5]. If the comparison costs are allowed to be arbitrary, one can not get good approximation ratios. A different way to assign costs is based on the idea that one can distill out an intrinsic value for each item being compared such that the cost of comparing two elements is some “well-behaved ” or “structured ” function of their values. We feel that mos