DocumentCode :
1711191
Title :
Sorting and selection with structured costs
Author :
Gupta, Anupam ; Kumar, Ajit
Author_Institution :
Lucent Technol. Bell Labs., Murray Hill, NJ, USA
fYear :
2001
Firstpage :
416
Lastpage :
425
Abstract :
The study of the effect of priced information on basic algorithmic problems was initiated by M. Charikar et al. (2000). The authors 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 Charikar et al. If the comparison costs are allowed to be arbitrary, we show that one cannot 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. The authors 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.
Keywords :
computational complexity; costing; sorting; theorem proving; trees (mathematics); approximation ratios; approximation results; associated cost; basic algorithmic problems; comparison costs; intrinsic value; practical applications; priced comparison model; priced information; sorting; structured cost model; structured cost property; structured costs; structured function; Computer science; Cost function; Databases; Robustness; Sorting;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Foundations of Computer Science, 2001. Proceedings. 42nd IEEE Symposium on
Print_ISBN :
0-7695-1116-3
Type :
conf
DOI :
10.1109/SFCS.2001.959916
Filename :
959916
Link To Document :
بازگشت