First Come First Served for Online Slot Allocation and Huffman Coding
Monik Khare, Claire Mathieu, Neal E. Young · 2013
Can one choose a good Huffman code on the fly, without knowing the underlying distribution? Online Slot Allocation (OSA) models this and similar problems: There are n slots, each with a known cost. There are n items. Requests for items are drawn i.i.d. from a fixed but hidden probability distribution p. After each request, if the item, i, was not previously requested, then the algorithm (knowing c and the requests so far, but not p) must place the item in some vacant slot ji, at cost pi c(ji). The goal is to minimize the total cost . The optimal offline algorithm is trivial: put the most probable item in the cheapest slot, the second most probable item in the second cheapest slot, etc. The optimal online algorithm is First Come First Served (fcfs): put the first requested item in the cheapest slot, the second (distinct) requested item in the second cheapest slot, etc. The optimal competitive ratios for any online algorithm are 1 + Hn–1 ∼ lnn for general costs and 2 for concave costs. For logarithmic costs, the ratio is, asymptotically, 1: fcfs gives cost opt + O(logopt). For Huffman coding, fcfs yields an online algorithm (one that allocates codewords on demand, without knowing the underlying probability distribution) that guarantees asymptotically optimal cost: at most opt + 2 log2(1 + opt) + 2.