CS 269S, Winter 2014: Theory Seminar
Bren Hall, Room 1423, 1pm
February 14, 2014:

First Come First Served for Online Slot Allocation and Huffman Coding

Jenny Lam

Presenting a paper by Monik Khare, Claire Mathieu, Neal E. Young

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 j_i , at cost p_i c(j_i). The goal is to minimize the total cost sum_i=(1 to n) p_i c(j_i).

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 + H_{n − 1} ∼ ln n for general costs and 2 for concave costs. For logarithmic costs, the ratio is, asymptotically, 1: fcfs gives cost opt + O(log opt).

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.