[Solved]: What is a clairvoyant algorithm?

Problem Detail: 

When talking about general data structure design, my lecture notes talk about one of the concerns being cost of operations. As well as the individual cost, it mentions amortized cost. But then it goes on to say:

Amortized cost can be:

• absolute (e.g. for every sequence σ of operations (O(n log n))
• competitive (e.g. for every sequence σ of operations O(OPT(σ)))

where OPT(σ) is the optimal cost of clairvoyant algorithms

I can't really make any sense of this. Googling throws up this but I can't see the relevance to data structures more generally. Can anyone help me understand the quoted text?

Asked By : 8128

Answered By : David Richerby

A clairvoyant algorithm is a (usually hypothetical) algorithm that can look into the future to guarantee that it makes the best possible decisions. The typical application is in so-called "online" problems, where the input must be processed as it arrives, before the whole input is known, or in other situations where an algorithm must act based on incomplete knowledge. The point is that the hypothetical clairvoyant algorithm would be able to make perfect decisions so you can use that as a benchmark to judge your real algorithm for the problem.

The example given in the page you link is for page replacement algorithms. You need to swap some page of virtual memory out to disk and, of course, you'd rather not swap out a page that's just about to be accessed. The hypothetical clairvoyant algorithm would know which page will not be needed for the longest time and will swap that one out; a real algorithm would have to estimate, for example by assuming that a page that has not been used for a long time will not be used again in the near future.

Now, you can do a comparison. Suppose you have enough physical memory to hold 1000 pages and you have a process that cycles through 1001 pages accessing them in the order 1, 2, ..., 1000, 1001, 1, 2, ... The real algorithm performs terribly in this case: when page 1001 is requested, it swaps out page 1, which is the very next page to be requested. In fact, the page the process requests is never in memory. A clairvoyant algorithm might, for example, keep pages 1–999 in memory all the time and swap in pages 1000 and 1001 as needed, giving page faults only 0.2% of the time.

Other applications of this sort of idea are things like process scheduling (in most cases, a real algorithm doesn't know what demands a process will make, so it must guess) and various auction schemes where the auctioneer uses the early bids to figure out what people are prepared to pay for an item, before selling it to the next highest bidder. The classic pop-science application is in deciding who you should marry which, for some reason, academics call the Secretary Problem. The clairvoyant algorithm would be to magically know who your ideal partner is and marry them; the best you can do in practice is to spend a few years dating and dumping people and then marry the next person you meet who is better than all the ones you dumped. (This carries the risk that you'll meet your ideal partner during the date-and-dump phase and then never meet anyone else that good; math doesn't always make your life better.)

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/20035