Skip to main content
eScholarship
Open Access Publications from the University of California

UC Riverside

UC Riverside Previously Published Works bannerUC Riverside

First come first served for online slot allocation and huffman coding

  • Author(s): Khare, M
  • Mathieu, C
  • Young, NE
  • et al.

Published Web Location

http://arxiv.org/pdf/1307.5296
No data is associated with this publication.
Abstract

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.

Many UC-authored scholarly publications are freely available on this site because of the UC's open access policies. Let us know how this access is important for you.

Item not freely available? Link broken?
Report a problem accessing this item