Sorting and selection with structured costs

The study of the effect of priced information on basic algorithmic problems was initiated by the paper of Charikar et al.. In this paper, we continue the study of sorting and selection in the priced comparison model, i.e., when each comparison has an associated cost, and answer some of the open problems suggested by [5]. If the comparison costs are allowed to be arbitrary, we show that 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 most practical applications will have some structured cost property. In this paper, we study the problems of sorting and selection (which includes finding the maximum and the median) in the structured cost model. We get a variety of approximation results for these problems, depending on the restrictions we put on the structured costs. We show that it is possible to get much improved results with the structured cost model than the case when we do not have any assumptions on comparison costs.