An Online Auction Example

• The maximum bid accepted by the offline algorithm is Poff

• If Poff is rejected by the online algorithm, at least 1/log ? resource was sold by the online for at least ½ Poff

• Offline – Online < Poff

• It follows that

Offline/Online < 1 + 2 * log ?

Previous slide

Next slide

Back to first slide

View graphic version