#
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.