Sorting and Selection with Random Costs

Details Sorting and Selection with Random Costs Sorting and Selection with Random Costs

2007-09-29

arxiv.org/abs/0710.0083v1

Computer Science

Data Structures and Algorithms

Scientific paper

There is a growing body of work on sorting and selection in models other than the unit-cost comparison model. This work is the first treatment of a natural stochastic variant of the problem where the cost of comparing two elements is a random variable. Each cost is chosen independently and is known to the algorithm. In particular we consider the following three models: each cost is chosen uniformly in the range $[0,1]$, each cost is 0 with some probability $p$ and 1 otherwise, or each cost is 1 with probability $p$ and infinite otherwise. We present lower and upper bounds (optimal in most cases) for these problems. We obtain our upper bounds by carefully designing algorithms to ensure that the costs incurred at various stages are independent and using properties of random partial orders when appropriate.

Affiliated with

Also associated with

No associations

Rating

Sorting and Selection with Random Costs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Sorting and Selection with Random Costs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Sorting and Selection with Random Costs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-462247