UC Riverside

Can one choose a good Huffman code on the fly, without knowing the underlying distribution? Online Slot Allocation (OS A) 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 Pic(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 4- Hn-1 ∼ In n 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 algo-rithm (one that allocates codewords on demand, without knowing the underlying probability distribution) that guarantees asymptotically optimal cost: At most OPT + 2 log2(l + OPT) + 2. Copyright © 2014 by the Society for Industrial and Applied Mathematics.