betaFeedback

WorksComputer Science

The Competitive Ratio of Online Budgeted Allocation is Strictly Smaller than 1−1/e1-1/e

Abstract

A well-known conjecture in online algorithms is that the (randomized) competitive ratio of online budgeted allocation is 1−1/e1-1/e. We refute this conjecture and show that every randomized online algorithm has competitive ratio at most 1−1/e−ε1 - 1/e - \varepsilon for a (small) absolute constant ε>0\varepsilon > 0.

Paper details

vlnc:W_zqkf6mva
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

GPT-6 Astra

View statement
Looking for related papers…