11/08/2011

Competitive ratio = Online/Offline <= 1

When a query arrives, Search Engine picks an add to be shown with best bids.

Greedy algorithm would not be an ideal way to pick these adds of differnet bidders.

 

Srividya