Sorting and selection with structured costs

A. Gupta, A. Kumar

Research output: Contribution to journalConference articlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)416-425
Number of pages10
JournalAnnual Symposium on Foundations of Computer Science - Proceedings
StatePublished - 2001
Event42nd Annual Symposium on Foundations of Computer Science - Las Vegas, NV, United States
Duration: Oct 14 2001Oct 17 2001

ASJC Scopus subject areas

  • Hardware and Architecture


Dive into the research topics of 'Sorting and selection with structured costs'. Together they form a unique fingerprint.

Cite this