Huffman Coding with Unequal Letter Costs
\numberofauthors{3} \alignauthor Mordecai J. Golin \thanks{ Partially supported by HK RGC Competitive Research Grants HKUST 6137/98E, 6162/00E and 6082/01E}
In the standard Huffman coding problem, one is given a set of words and for each word a positive frequency. The goal is to encode each word $w$ as a codeword $c(w)$ over a given alphabet. The encoding must be prefix free (no codeword is a prefix of any other) and should minimize the weighted average codeword size \(\sum_{w} \freq w\, \size{c(w)}\). The problem has a well-known polynomial-time algorithm due to Huffman \cite{Huff-52}. Here we consider the generalization in which the letters of the encoding alphabet may have non-uniform lengths. %, as in the dots and dashes of Morse Code. The goal is to minimize the weighted average codeword length \(\sum_{w} \freq w\, \cost{c(w)}\), where $\cost s$ is the sum of the (possibly non-uniform) lengths of the letters in $s$. Despite much previous work, the problem is not known to be NP-hard, nor was it previously known to have a polynomial-time approximation algorithm. Here we describe a polynomial-time approximation scheme (PTAS) for the problem.
STOC_Final.tex
%update: Neal Mon Feb 18
%update: Mordecai Fri Feb 15 22:22:39 HKT 2002
%update: Mordecai Mon Nov 12 22:19:46 HKT 2001
%Update: Claire Mon Nov 12
%update: Mordecai Mon Nov 12 15:15:02 HKT 2001
%update: Claire Nov 10 2001
%update: Mordecai Nov 10 2001
%update: Neal Nov 8 2001
%update: Mordecai Nov 6 2001
%update: Claire Nov 1 2001
%update: Neal Sept 30 2001
%Previous update: Claire Sept 28 2001
%\documentclass[11pt]{article}
%\documentclass[11pt]{report}
%\documentclass[11pt,titlepage]{article}
%\documentclass[11pt]{article}
%\documentclass{sig-alt-full}
\documentclass{acm_proc_article}
\usepackage{algorithm}
\usepackage[noend]{algorithmic}
        \newcommand{\INPUT}{\item[\algorithmicinput]}
        \newcommand{\OUTPUT}{\item[\algorithmicoutput]}
        \newcommand{\algorithmicinput}{\textbf{INPUT:}}
        \newcommand{\algorithmicoutput}{\textbf{OUTPUT:}}

%\usepackage{fullpage}
%\usepackage{graphicx}

\newtheorem{Theorem}{Theorem}
\newtheorem{Definition}{Definition}
\newtheorem{Definitions}[Definition]{Definitions}
\newtheorem{Lemma}{Lemma}
\newtheorem{Assumption}{Assumption}
\newtheorem{Corollary}[Lemma]{Corollary}
\newtheorem{Observation}[Lemma]{Observation}

\renewcommand{\footnote}[1]{}

\newcommand{\size}[1]{|{#1}|}
\newcommand{\cost}[1]{\mbox{\rm cost}({#1})}
\newcommand{\freq}[1]{\mbox{\rm freq}({#1})}

\newcommand{\R}{{\sf R\hspace*{-0.9ex}\rule{0.15ex}{1.5ex}\hspace*{0.9ex}}}
\newcommand{\Rp}{\R_+}
\newcommand{\N}{{\sf N\hspace*{-1.0ex}\rule{0.15ex}{1.3ex}\hspace*{1.0ex}}}
\newcommand\eps\varepsilon
\newcommand{\enc}[1]{\mbox{\rm enc}({#1})}

\newcommand{\elltwo}{1}

%\newcommand{\def}{\em}
\newcommand{\defn}{\bf}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}
\conferenceinfo{STOC'02,} {May 19-21, 2002, Montreal, Quebec, Canada.} 
\CopyrightYear{2002} 
\crdata{1-58113-495-9/02/0005} 
\title{Huffman Coding with Unequal Letter Costs}
\subtitle{[Extended Abstract]}

\author{
\numberofauthors{3}
\alignauthor Mordecai J. Golin
\thanks{
Partially supported by HK RGC Competitive 
Research Grants HKUST 6137/98E, 6162/00E and 6082/01E}\\
        \affaddr{Hong Kong UST} 
        \affaddr{Clear Water Bay}
        \affaddr{Kowloon, Hong Kong}
        \email{golin@cs.ust.hk}
\alignauthor Claire Kenyon\\ 
        \affaddr{Laboratoire de Recherche en Informatique (LRI)}
        \affaddr{Universit\'e Paris-Sud}
        \affaddr{France}
        \email{kenyon@lri.fr}
\alignauthor  Neal E. Young\\
        \affaddr{Akamai Technologies} 
        \affaddr{Cambridge, MA}
        \affaddr{USA}
        \email{neal@young.name}
}
\maketitle

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{abstract}
  In the standard Huffman coding problem, one is given a set
  of words and for each word a positive frequency.  The goal
  is to encode each word $w$ as a codeword $c(w)$ over a given
  alphabet.  The encoding must be prefix free (no codeword is
  a prefix of any other) and should minimize the weighted
  average codeword size \(\sum_{w} \freq w\, \size{c(w)}\).
  The problem  has a well-known polynomial-time algorithm 
  due to Huffman \cite{Huff-52}. 
  
  Here we consider the generalization in which the letters of
  the encoding alphabet may have non-uniform lengths.
  %, as in the dots and dashes of Morse Code.  
  The goal is to minimize
  the weighted average codeword length \(\sum_{w} \freq w\,
  \cost{c(w)}\), where $\cost s$ is the sum of the (possibly
  non-uniform) lengths of the letters in $s$.  Despite
  much previous work, the problem
  is not known to be NP-hard, nor was it previously known to
  have a polynomial-time approximation algorithm.  Here we
  describe a polynomial-time approximation scheme (PTAS) for
  the problem.
\end{abstract}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Introduction}
  
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\begin{figure*}[t]
\label{Fig:example}
\centering
\epsfig{file=New_Example.eps,width=\hsize}
\caption{Two minimum-cost codes   for the frequencies
$(p_1,p_2,p_3,p_4) = (2,2,1,1)$
 but under different alphabets. Codes are represented using the
standard tree format with leaves signifying codewords. The left tree 
is for $\Sigma = \{0,1\}$ with $\ell_1 = cost(0) = 1$ and
$\ell_2 = cost(1)=1$.
The right tree is for $\Sigma=\{ a , b \}$ with 
 $\ell_1= cost(a) = 1$ and $\ell_2= cost(b)=3$. The four codewords encoded
by the left tree are $\{00,01,10,11\};$ the cost of the code
is  $2 \cdot 2 + 2 \cdot 2 + 1 \cdot 2 + 1 \cdot 2 = 12.$
The four codewords encoded
by the right  tree are $\{aaa, aab, ab, b\};$
the cost of the code
is $2 \cdot 3 + 2 \cdot 3 + 1 \cdot 4 + 1 \cdot 5 = 21.$
}
\end{figure*}



Given a set of $W$ of $n$ words with associated probabilities or
frequencies
\(p_1 \ge p_2 \ge \cdots \ge p_n >0\) and an {\em encoding
  alphabet} $\Sigma$, the {\em prefix coding} problem,
sometimes known as the {\em Huffman encoding} problem is to
find a prefix-free code over $\Sigma$ of minimum cost. This
problem is very well studied and has a well-known
%$O(n \log n)$-time greedy algorithm due to Huffman \cite{Huff-52}.
$O(n)$-time greedy algorithm due to Huffman \cite{Huff-52}
($O(n \log n)$ if the $p_i$ are not sorted in advance).

Here we consider the generalization of the problem in
which the letters used for encoding can have different costs.
That is, letting $r=|\Sigma|$, the $r$ letters have associated
costs \(\ell_1 \le \ell_2 \le \cdots \le \ell_r\) and the cost
of a codeword is defined to be the sum of the costs of its
letters (rather than the length of the codeword).


For an example of the problem we are addressing refer to Figure
\ref{Fig:example}.  Both  codes  have minimum cost  for the frequencies
$(p_1,p_2,p_3,p_4) = (2,2,1,1)$ but under  different letter
costs.  The code   $\{00,01,10,11\}$
has  minimum cost for the standard Huffman case
of $\Sigma = \{0,1\}$ in which the length of each letter is 1,
i.e., the cost of a word is the number of bits it has.
The code  $\{aaa, aab, ab, b\}$ has
minimum cost for the alphabet $\Sigma=\{a , b\}$
in which the length of a ``$a$'' is 1 and the length of a ``$b$'' is 3.

This generalization is motivated by
coding problems  in which  different characters have 
different transmission times or storage costs
\cite{Blach-54, Marcus-57, Karp-61, Stan-70, Varn-71}.
One example is the {telegraph channel}
\cite{gilb-69, gilb-95} in which $\Sigma=\{ \cdot , - \}$ and
$\ell_2=2\ell_1$, i.e., 
in which dashes are twice as long as dots.  Another
is the $(a,b)$ run-length-limited codes used in magnetic and optical storage
\cite{Imm-99,GR-98},
in which the codewords are binary and constrained
so that each {\bf 1} must be preceded by at least $a$, and at most
$b$, {\bf 0}'s.
(This example can be modeled by the problem studied here
by using an encoding alphabet of $r=b-a+1$ characters 
$\{0^k 1 : k=a,a+1,\ldots,b\}$
with associated costs $\{\ell_i = a+i-1\}$.)

The literature contains many algorithms for the generalized problem.
The special case when all the {\em probabilities} are equal
(but not the letter lengths), known
as the Varn coding problem, is solvable in polynomial-time
\cite{Varn-71, LEC-73, Cot-75, PGE-75, GY-94, CG-96}.
For the generalized problem,
Blachman \cite{Blach-54}, Marcus \cite{Marcus-57},
and (much later) Gilbert \cite{gilb-95}
give heuristic constructions.  Karp gave
the first algorithm yielding an exact solution (assuming the letter costs are integers);
Karp's algorithm transforms the problem into an integer
program and does not run in polynomial time \cite{Karp-61}.
Karp's result was followed by many others
\cite{Krause-62, Csiszar-69, Cot-77, Mehlhorn-80, AM-80}
presenting solutions of cost at most $\mbox{OPT} + f(\ell_1,\, \ell_2,\, \ldots,\,  \ell_r)$
where $\mbox{OPT}$ is the cost of the optimal code and 
$f(\ell_1,\, \ell_2,\, \ldots,\,  \ell_r)$ is some fixed
function of the edge costs, with the different algorithms having
different $f(\cdot)$ (note that for these results the $p_i$ are
considered to be probabilities that sum to 1).
\iffalse
These results do not imply a PTAS for the problem
--- even with fixed letter costs. 
because the problem is not trivial even when $\mbox{OPT} = O(1)$.)
These algorithms
essentially demonstrate that a generalized
version of entropy is a lower bound on the code cost and then design algorithms
that construct codes within an additive function
%\footnote{NEY:
%changed ``additive constant'' to ``additive function''}
of that entropy.  
\fi
These algorithms
essentially demonstrate that a generalized
version of entropy is a lower bound on the code cost and then design algorithms
that construct codes within an additive function of that entropy.
They do not imply imply a PTAS for the problem, though, 
even with fixed letter costs. 
Golin and Rote \cite{GR-98} gave a
dynamic programming algorithm that produces exact solutions in 
$O(n^{\ell_r+2})$ time for the special case when the $\ell_i$ are restricted to be integers.
Bradford et.\ al.~\cite{BGLR-98}  improved this to 
$O(n^{\ell_r})$  when $r=2.$  

For further references on Huffman coding with unequal letter costs, 
see Abrahams' recent survey on source coding
%\cite[Section 2.7, {\em Coding with Unequal Cost Code Symbols: The Karp Problem}]{Abrahams-01},
\cite[Section 2.7]{Abrahams-01},
which contains a section on the problem.
%\footnote{NEY:
%  we have not defined the ``unequal-cost coding problem''?}

Despite the extensive literature, 
there is no known polynomial-time algorithm for the
%general problem of Huffman coding with a variable-length alphabet,
generalized problem, nor is the problem known to be NP-hard.  
Before this work, the problem was not known to
have any polynomial-time approximation algorithm.
Our main result here is a polynomial-time approximation
scheme (PTAS) for the problem:
        \footnote{ 
        MJG: $c(\epsilon) = \exp(O(\ln(1/\epsilon)/\epsilon^2))$
seems to be left over from an earlier version.  From Lemma 7 
the number of groups is $O(k/\epsilon^2)$ and the number
of levels we need to guess in the $k$-prefix code is
$k/\epsilon$ so the total number of guesses made by the exhaustive
search in algorithm 2 should be
$c(\epsilon) = \exp(O(k/\epsilon^2) \cdot O(\log (k/\epsilon) ))
= \exp(O(\ln^2(1/\epsilon)/\epsilon^3)).$

CK: let's wait until monday to put in the proper power of 1/epsilon ...
this may change again over the weekend...
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{Theorem}\label{main_theorem}
  Given an instance $((p_i),(\ell_j))$ of the Huffman
  coding problem with unequal letter costs, and given a
  positive $\epsilon$, there exists
  an algorithm that constructs a prefix code of cost
  at most $(1+\eps)\mathrm{OPT}$; this algorithm runs in time
  $nd\log(n)\exp(O(\ln(1/\epsilon)^2 /\epsilon^2))$,
  where $d$ is the number of distinct letter costs. 
\end{Theorem} 
\footnote{The $O(n^2)$ term is the cost for the algorithm when 
$\eps \le \ell/n.$}
The algorithm is based on a new relaxation of Huffman coding
with unequal letter costs.  The relaxation, called the {\em $k$-prefix code problem},
allows codewords of cost
more than $k$ to be prefixes of other codewords.  
%The algorithm uses straightforward grouping and enumeration techniques
The algorithm uses  grouping and enumeration techniques
to find a near-minimum-cost $k$-prefix code (where
$k$ is a constant depending only on $\epsilon$), and then
converts this $k$-prefix code into a true prefix code
%using a ``rounding scheme'' that increases the cost by at most a
increasing the cost by at most a $1+O(\epsilon)$ factor.

The techniques introduced in this paper can also be used to 
construct PTAS's for the {\em regular-language prefix-coding}
problem, a different generalization of Huffman coding
that asks for a minimum-cost prefix code under the 
additional restriction that all codewords belong to a given regular
language $\cal L$.  As one  example, the binary codes, constrained
so all codewords must end in a {\bf 1},
are used for group testing and the construction of 
self-synchronizing codes \cite{BY-90,CSP-94}. As another example,
binary codes whose codewords contain at most a specified
number of {\bf 1}'s are used for energy minimization
of transmissions in mobile environments \cite{DKY-99}.
Algorithms (other than exhaustive search) for
the regular-language prefix-coding problem
generalize \cite{GR-98} and run in time
$n^{\Theta(S({\cal L}))}$ where $S({\cal L})$ is the 
number of states in the smallest 
deterministic finite automaton that accepts $\cal L$.
{In this extended abstract we do 
  not discuss how the techniques here extend to
  that problem.}

{\em Alphabetic} coding is like the generalized problem
considered here, but with an additional constraint on the
code: the codewords must be chosen in increasing alphabetic
order (with respect to the words to be encoded).  
This problem arises in designing testing procedures
in which the time required by a test depends upon the outcome
of the test \cite[6.2.2, ex.\ 33]{Knuth-73} 
and has also been studied under the names {\em dichotomous
  search} \cite{Hind-90} or the {\em leaky shower} problem \cite{kr-89}.  
Alphabetic coding has a polynomial-time algorithm \cite{Itai-76}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Notations and definitions}

A problem instance is specified by a set $W$ of $n$ words with associated frequencies 
\(p_1\ge p_2 \ge \cdots \ge p_n >0\), an alphabet $\Sigma$ of
\(r\ge 2\) letters with associated costs \(\ell_1 \le \ell_2
\le \cdots \le \ell_r\), and an $\epsilon>0$.
The {\em Huffman coding problem with unequal letter costs}
is the problem of finding a prefix code of minimum cost.

\begin{Definitions}
  A {\defn code} (usually denoted $c$) is an injective map
  from  $W$ to $\Sigma^*$.  Its image $c(W)$ is called the
   set of {\defn codewords of $c$}.  
   A set $S \subset \Sigma^*$ is {\defn prefix-free}
  if no element of $S$ is a prefix of any other element of
  $S$; a {\defn prefix code} is one whose set of
  codewords is  prefix-free.  The {\defn cost} of a code $c$ is \(\sum_{i=1}^n
  p_i\, \cost{c(w_i)}\), where $\cost{x}$ is the sum of the costs
of the letters of $x$.
\end{Definitions}


Unless otherwise stated, all the codes considered here are
{\bf ordered}, i.e.\ the map $c$ assigns codewords of smaller
costs to words of larger probability:
$\cost{c(w_1)}\le\cost{c(w_2)}\le\cdots\leq\cost{c(w_n)}$.
Clearly, any optimal code must be ordered.

\begin{Definition}
  A {\defn $k$-prefix code} is a code in which no codeword
  of cost less than $k$ is a prefix of any other codeword.
\end{Definition}
One of the main reasons that prefix-codes are useful is that
they are uniquely decipherable.  A $k$-prefix code is in
general not uniquely decipherable and therefore not
particularly useful by itself. The problem of designing a
$k$-prefix code is introduced and used here solely as an
intermediate tool for solving the original problem.

\medskip

We generally use $w$ to denote a word to be encoded, $x$ to
denote a potential codeword (a string in $\Sigma^*$),
\(\cost x\) to denote the sum of the costs of the letters in
$x$'s, and \(\size x\) (the {\defn size} of $x$) to denote the
number of letters.  To distinguish the given words $W$ from
the potential codewords $\Sigma^*$, we call the former {\defn words}
and the latter {\defn
  strings}. 
We use $d$ to denote the number of distinct letter costs.

The following assumption about the input is convenient:

\begin{Assumption}\label{assumptions}
  Each $\ell_i$ for $i\ge 2$ is an integer multiple of $\epsilon$,
  $\ell_2$ equals $1$, and $\epsilon$ is either an integer multiple of $\ell_1$
  or evenly divides $\ell_1$, 
  Thus, all codeword costs are integer multiples of $\min\{\ell_1,\epsilon\}$.
\end{Assumption}
It is also without loss of generality:
\begin{Lemma}\label{scaling}
  The following reduction reduces any problem instance
  to an instance satisfying Assumption~\ref{assumptions}:
  \\ 1. Scale the $\ell_i$'s uniformly to make  $\ell_2=1$.
  \\ 2. Decrease $\epsilon$ to its next smallest multiple, or divisor, of $\ell_1$.
  \\ 3. Increase each $\ell_i$ for $i\ge 2$ to its next largest multiple of $\epsilon$.
  \\4.  Scale the $\ell_i$'s, and $\epsilon$, uniformly to make $\ell_2=1$.
\end{Lemma}
\begin{proof}
  Step 2 decreases $\epsilon$ by at most a factor of 2.
  Step 3 increases the cost of any solution by at most
  a $1+\epsilon$ factor.
  Step 4 decreases $\epsilon$ by at most a factor of $1+\epsilon$.
\end{proof}

In the main sections
(particularly Lemmas~\ref{lem:size_D} and~\ref{complexity1})
we also assume that $\ell_1>\epsilon/n$.
The special case $\ell_1\leq \epsilon/n$ is easy and is dealt with in 
Section~\ref{sec:l1_tiny}.


Before we explain the main algorithm
(Algorithm~\ref{alg:main}), we first explain two subroutines
used in that algorithm:
Algorithm~\ref{alg:construct} for constructing a so-called {\em leveled}
$k$-prefix code meeting certain constraints,
and Algorithm~\ref{alg:convert} for converting such a code
into a true prefix code.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Finding an optimal $k$-prefix code}

Algorithm~\ref{alg:construct} finds an optimal $k$-prefix
code meeting some given constraints.  The first constraint is
that the code should be {\em leveled}:

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{algorithm}[t]
  \caption{-- builds a leveled $k$-prefix-free set of codewords 
    given the level 0 codeword and the number of codewords per level.
    }
    \label{alg:construct}
  \begin{algorithmic}[1]
    \smallskip

    \INPUT Letter costs,  directed graph $D$,
    constraints $(f(0),f(1),\ldots,f((k-1)/\epsilon))$.
    \smallskip
    
    \OUTPUT  leveled $k$-prefix code with $f(i)$
    codewords in each level $i\geq 1$ and a codeword in level zero of
    size $f(0)$ (if $f(0)>0$).  (Or ``inconsistent'' if no such code exists.)

    \smallskip
    \STATE \label{line:1} $S\leftarrow\emptyset$
    
    \STATE \label{line:define} For any node $\ell$ of $D$,
    define $v_S(\ell)$ to be the number of strings of cost
    $\ell$ having no prefix in $S$.
    (The algorithm will build a table $v$ with $v[\ell] = v_S(\ell)$ as it proceeds.)

    \STATE \label{line:f(0)}
    If $f(0)>0$, then $S\leftarrow \{ a^{f(0)} \}$
    ($a$ is the smallest letter).

    \STATE \label{line:initv}
    For each node $\ell$ on
    level $0$, initialize $v[\ell]$:
    \\$v[\ell]=1$ if $\ell < f(0)$ or $f(0)=0$;
    $v[\ell]=0$ otherwise.
    
    \FOR{$i=1,2,\ldots,(k-1)/\epsilon$}\label{line:for}
    
    \STATE\label{line:4}
    For each node $\ell$ of $D$ in level
    $i$, by order of increasing costs,
    initialize $v[\ell]$ using the recurrence
    $v_S(\ell) = \sum_{i=1}^r v_S(\ell-\ell_i)$.
    \label{line:4bis} 

    \STATE \label{line:5} 
    Let $\ell = \elltwo+i\epsilon - \min\{\ell_1,\epsilon\}$.
    If $v[\ell] < f(i)$, then return ``inconsistent''.
    Otherwise, choose $f(i)$ codewords of cost $\ell$
    and add them to $S$.  Decrement $v[\ell]$ by $f(i)$.
    \ENDFOR

    \STATE \label{line:7}
    Complete $S$ by adding $n-|S|$ strings of minimum cost among the strings of cost
    \(\ge k\) that don't have a prefix of cost $< k$ in $S$.
    If $|S|<n$ and there aren't any such strings, return ``inconsistent''.
    (Find the $n-|S|$ strings by extending $D$ as needed beyond cost $k$.)

    \STATE Return the set of codewords $S$.
  \end{algorithmic}
\end{algorithm}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{Definitions}\label{def:leveled}
  For $i\in \{ 1,\ldots,(k-1)/\epsilon \}$, define the $i$th {\defn level
    of $\Sigma^*$} to be the set of strings $x$ such that %$|x| \le n$ and
  $\elltwo+(i-1)\epsilon \le \cost x < \elltwo+i\epsilon$.
  Define level 0 to be the set of strings
  that cost less than $\elltwo$.

  A code is {\defn maximal within level $i$} if
  every codeword in level $i$ is of cost 
  $\elltwo+i\epsilon - \min\{\ell_1,\epsilon\}$.

  A code is {\defn leveled} if it is maximal within all levels.
\end{Definitions}
Note that level 0 can only contain words of $a^*$, where $a$ is the
letter of cost $\ell_1$.
Note also that by assumption either
(i)  $\ell_1$ is an integer multiple of $\epsilon$,
in which case each level $i>0$ consists of the strings of cost
$\elltwo+(i-1)\epsilon$ and every code is trivially maximal,
or (ii) $\ell_1$ evenly divides $\epsilon$,
in which case every string in level $i$
has cost $\elltwo+(i-1)\epsilon + j\ell_1$
for some integer $j \le n$.

The second constraint that the constructed codeword must meet
is specified by a tuple $f = (f(0),\cdots,f((k-1)/\epsilon ))$ of integers,
with the following meaning.
\begin{enumerate}
\item 
If $f(0)=0$, then there must be no codeword in level 0; if $f(0)>0$, then
the set of codewords must contain the codeword $a^{f(0)}$ from level 0.
\item
For every level $i>1$, the set of codewords must contain 
exactly $f(i)$ codewords
in level $i$.
\end{enumerate}

Algorithm~\ref{alg:construct}
uses a directed graph $D$
that is computed by Algorithm~\ref{alg:main}
and given to Algorithm~\ref{alg:construct} as input.
The nodes of $D$ are all possible codeword costs
in $[0,k]$, with an arc from $\ell$ to $\ell'$ if and only if
$\ell'-\ell\in \{ \ell_1,\elltwo,\cdots,\ell_r \}$.

Here is the performance guarantee of Algorithm~\ref{alg:construct}:
\begin{Lemma}\label{lemma:construct}
  Given a constraint
  $f=(f(0),\ldots,f((k-1)/\epsilon))$, if there exists a leveled $k$-prefix code
  consistent with the constraint, then Algorithm~\ref{alg:construct}
  constructs one of minimum cost.
\end{Lemma}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{proof}
  It is straightforward to verify that
  Algorithm~\ref{alg:construct}
  correctly computes each $v_S(\ell)$
  and produces a leveled $k$-prefix code consistent with the constraint,
  if one exists.

  Among the codes meeting the constraints of being 
  leveled and consistent with $f$, the chosen code has
  minimum cost because the cost of codewords on
  levels $0,1,\ldots,(k-1)/\epsilon$ is determined by those
  constraints, and, given the codewords in those levels, the
  chosen code takes a set of codewords of cost $\ge k$ of
  minimum possible cost.
\end{proof}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Converting a $k$-prefix code into a prefix code}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Algorithm~\ref{alg:convert} converts a $k$-prefix code into a prefix code.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{algorithm}[t]
  \caption{--- converts a $k$-prefix code into a prefix code}
  \label{alg:convert}
  \begin{algorithmic}[1]
    \smallskip
    \INPUT letter costs; $k$-prefix code $c$
    \OUTPUT prefix code $c'$
    \smallskip
    \STATE
    Let $a$ and $b$ be the letters of cost $\ell_1$ and
    $\ell_2$, respectively.
    \STATE
    For positive integer $i$,
    define $\enc i = b'_1b'_1 b'_2b'_2b'_jb'_jab$
    where $b'_1 b'_2 \ldots b'_j$ is obtained from the binary 
    representation $b_1 b_2 \ldots b_j$ of $i$
    by replacing each ``$0$'' with ``$a$'' and each ``$1$''  with $b$.
    Define $\enc 0 = ab$.
    \FOR{each codeword of cost $\ge k$}
    \STATE
    Let $\alpha$ be the smallest prefix of cost $\ge k$
    and $\beta$ the remaining suffix.
    Replace the codeword by
    $\alpha\,\enc i\beta\,b$,
    where $i$ is the number of $b$'s in $\beta$.
    \ENDFOR
    \STATE Return the modified code.
  \end{algorithmic}
\end{algorithm}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
The next lemma captures what we need to know about Algorithm~\ref{alg:convert}
in order to use it in the main algorithm (Algorithm~\ref{alg:main}):

\begin{Lemma}\label{lemma:convert}
  Given any $k$-prefix code $c$ of cost $\alpha$,
  Algorithm~\ref{alg:convert} constructs a prefix code $c'$ of cost
  at most $\alpha[1+\ell_2(5+2\log_2 k)/k]$.
\end{Lemma}

\begin{proof}
  First we analyze the cost.
  Let $c(w)=\alpha\beta$ and $c'(w)=\alpha\,\enc i\beta\,b$,
  respectively, be an original and modified codeword
  in Algorithm~\ref{alg:convert}.
  From $i\le \cost{\beta}$ it follows that
  \(\cost{c'(w)} \le \cost{c(w)} + \ell_2[5+2\log_2 \cost{c(w)}]\).
  Since $\cost{c(w)} \ge k$ if the codeword is modified, each modified codeword
  costs at most $1+\ell_2(5+2\log_2 k)/k$ times
  as much as the original.

  Next we show that $c'$ is prefix free.
  Suppose $c'(v)$ is a prefix of $c'(w)$ for some $v,w\in W$.
  Since the original code was $k$-prefix free, it must be that
  $$\begin{array}{llll}
    &c'(v)&=&\alpha\, \enc{i}\beta b\\
    \mathrm{and~~}&c'(w)&=&\gamma\, \enc{j}\delta b
  \end{array}$$
  where $\alpha$ and $\gamma$ each have cost $\ge k$
  but have no proper prefix of cost $\ge k$,
  and where $i$ and $j$ are the number of $b$'s in
  $\beta$ and $\delta$, respectively
  (as in Algorithm~\ref{alg:convert}).
  Since $c'(v)$ is a prefix of $c'(w)$,
  $\alpha$ is a prefix of $c'(w)$,
  which means $\alpha = \gamma$.
  Thus, $\enc{i}$ is a prefix of $\enc{j}\delta b$.
  Since every letter in $\enc{}$ is doubled
  except the last two, it must be that $i=j$.
  Thus, $\beta b$ is a prefix of $\delta b$.
  But (since $i=j$) $\beta$ has the same number of $b$'s as $\delta$,
  so it must be that $\beta = \delta$.
  Finally, we can conclude that $\alpha \beta = \gamma \delta$.
  Since these were the original codewords assigned to $v$ and $w$,
  it must be that $v=w$.

\end{proof}
%%%%%%%%%%%%%%%%%%%%%%%%
\section{The main algorithm}
%%%%%%%%%%%%%%%%%%%%%%%%

The main algorithm is Algorithm~\ref{alg:main}. It consists of:
\begin{enumerate}
\item\label{phase1}
Some preprocessing
(Steps~\ref{step:round},~\ref{step:init},~\ref{step:graph},
and~\ref{step:group}).
\item\label{phase2}
Calling Algorithm~\ref{alg:construct} for
$O_\epsilon(1)$
different constraint tuples $(f(0),\ldots ,f((k-1)/\epsilon ))$ 
(Steps~\ref{step:search},~\ref{step:for},~\ref{step:for2}).
\item\label{phase3}
Choosing the best $k$-prefix code among those output by
Algorithm~\ref{alg:convert}, transforming it into
a prefix code (Step~\ref{step:convert}),
and returning the resulting code.
\end{enumerate}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{algorithm}[t]
  \caption{--- finds a $(1+O(\epsilon))$-optimal prefix code}\label{alg:main}
  \begin{algorithmic}[1]
    \smallskip
    
    \INPUT
    Set $W$ of words with frequencies \(p_1\geq p_2\geq \cdots \geq p_n>0\);
    letter costs \(\ell_1\leq \ell_2\leq\cdots \leq \ell_r\);
    \(\eps >0\).  \smallskip

    \OUTPUT
    prefix code of cost at most $(1+O(\epsilon))\mathrm{OPT}$
    \smallskip
    
    \STATE \label{step:round} 
    Adjust $\epsilon$ and the $\ell_i$'s so that
    $\ell_2=1$, $\epsilon$ is an integer divisor or multiple
    of $\ell_1$, and each $\ell_i$ for $i\ge 2$ is a multiple
    of $\epsilon$ (as in Lemma~\ref{scaling}).

    \STATE \label{step:init} Choose
    $k=\Theta(\log(1/\epsilon)/\epsilon)$ so $k-1$ is a
    multiple of $\epsilon$.
    
    \STATE \label{step:graph}
    Construct a directed graph $D$ whose nodes are all
    codeword costs in $[0,k]$, with an arc from $\ell$ to $\ell'$ iff
    $\ell'-\ell\in \{ \ell_1,\ell_2,\cdots,\ell_r \}$.  Do
    this by enumerating the vertices and edges of $D$ using
    breadth-first search from the root (node 0).
    
    \STATE \label{step:group} Greedily partition $W$ into groups.
        \begin{itemize}
        \item
        The first group is $G_1=\{ w_1 \}$.
        \item
        Take $i$ maximum such that $p_i>(1-p_1)\epsilon^2/(2k)$. Then
        $G_2=\{ w_2 \}$, $G_3=\{ w_3 \}$, $\ldots$, and $G_i=\{ w_i \}$. 
        \item
        While $W$ is not empty, greedily take for the next group
        $\{ w_j,w_{j+1},\ldots ,w_\ell \}$, where
        $p_j+\cdots +p_\ell\leq (1-p_1)\epsilon^2/k < p_j+\cdots +p_{\ell+1}.$
        \end{itemize}

    \STATE \label{step:search} By exhaustive search, guess
    whether there is a codeword of cost $<1$ and what its size
    is (call it $f(0)$), and, for each
    $i=1,2,\ldots,(k-1)/\epsilon$, guess which groups will be
    assigned to level $i$ (i.e., with costs in
    $[\elltwo+\eps (i-1), \elltwo+\eps i)$) and let $f(i)$ denote the
    total number of words in those groups.  

    \FOR{each such guess $(f(0),\ldots ,f((k-1)/\epsilon ))$}\label{step:for}

    \STATE Use
    Algorithm~\ref{alg:construct} to construct an optimal
    $k$-prefix code consistent with the guess (if one
    exists).  \label{step:for2}

    \ENDFOR

    \STATE\label{step:best}
    Let $c$ be the minimum-cost code constructed.
    
    \STATE \label{step:convert}
    Using Algorithm~\ref{alg:convert}, convert $c$ into a
    prefix code $c'$.  

    \STATE Return $c'$.
  \end{algorithmic}
\end{algorithm}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Next we analyze the cost of the code produced.

%%%%%%%%%%%%%%%%%%%%%%%%%%
\iffalse%NEY replaced with lemma 1
\begin{Lemma}
  To find a $1+O(\epsilon)$-optimal solution to the original problem,
  it suffices to find a $1+O(\epsilon)$-optimal solution to
  the problem as modified by Step~\ref{step:round}.
\end{Lemma}

\begin{proof}
  Standard scaling and rounding arguments.
\end{proof}
\fi

%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{Lemma}\label{grouping}
Step~\ref{step:group} partitions $W$ into $O(k/\epsilon^2)$
groups.
\end{Lemma}

\begin{proof}
  Take any two consecutive groups other than $G_1$. The
  cumulative probability of the words in the two groups is at
  least $(1-p_1)\epsilon^2/(2k)$. Thus there can be at most
  $1+4k/\epsilon^2$ such groups.
\end{proof}

%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{Lemma}\label{lb}
$OPT\geq 1-p_1$.
\end{Lemma}

\begin{proof}
At most one codeword can belong to $a^*$. All the other codewords contain
at least one letter which costs at least 1, and their cumulative
frequency is at least $1-p_{\max}=1-p_1$.
\end{proof}


We now focus on
Steps~\ref{step:search} through~\ref{step:best}.
The analysis of Algorithm~\ref{alg:construct}
implies that these find a code that is optimal among 
leveled $k$-prefix codes meeting the grouping constraints
(mapping elements within each group to the same level).
The next lemma implies that
this code has cost at most $1+O(\epsilon)$ times the minimum
cost of any $k$-prefix code.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{Lemma}\label{lemma:existence}
  For any $k$-prefix code $c$, there exists a
  leveled $k$-prefix code $c'$ that maps group elements within
  each group to the same level, and such that \(\cost{c'} \le
  \cost c (1 + O(\eps)).\)
\end{Lemma}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{proof}
Let $c$ be an optimal $k$-prefix code.
We modify $c$ level by level so 
 that for each $i$, $c$ is maximal within level $i$
and so that level $i$ contains all or none of the elements of each group,
as follows. 
Since level 0 contains at most one codeword, and the first group
contains exactly one element, this is already true for level 0.
Assume that we have already modified $c$ to guarantee those
properties for levels up to $i-1$, and consider level $i$. 

{\bf Leveling phase for level $i$.} First
modify $c$ so that it is maximal within level $i$
by taking every codeword $z$ in level $i$
and padding it with enough $a$'s (i.e., replace $z$ by $za^j$)
so that its cost is $\elltwo+i\epsilon-\min\{\ell_1,\epsilon\}$, i.e. so that
adding one more letter $a$ would move the codeword out of level $i$.
(Here we use the assumption that every letter cost 
is a multiple of $\epsilon$,
with the possible exception of $\ell_1$ which then evenly
divides $\epsilon$.)

{\bf Grouping phase for level $i$.} Next modify the code so that
level $i$ contains all or none of the elements of each group
(i.e., no group is ``split'').
                                %NEY -- tried to simplify
                                %this, hope it's okay,
                                %restore the iffalse if not
%NEY START
By induction, no group is split in levels $0,\ldots,i-1$.
Since the code is ordered, at most one group can be split from
level $i$.  Take each codeword in that group and on level $i$
and pad it with an $a$ to move it out of level $i$.  Then, if
necessary, reorder the code (on levels greater than $i$).

When this construction has been done for every $i$, the
original $k$-prefix code $c$ has been changed into a leveled
$k$-prefix code $c'$ that maps elements within each group to
the same level.  Next we show that the cost of $c'$ is
$1+O(\epsilon)$ times the cost of $c$.

First consider a codeword that is padded in the leveling phase
for some level $i$ but not in the grouping phase for that
level.  Since each codeword has this happen at most once, and
the operation increases the cost of the codeword by at most
$\epsilon$ times the original cost of the codeword, the total
increase in cost due to such operations is at most $\epsilon$
times the original cost of the code.

Next consider codewords that are padded in the grouping
phases.  In the leveling and grouping phases for a given level
$i$, the cost of a codeword is increased by at most
$\epsilon+\ell_1\le 2$.  Since only one group is padded in the
grouping phase, and (by the grouping criterion) the group has total
probability at most $(1-p_1)\epsilon^2/k$, the total increase
in cost of all codewords in the group during the leveling and
grouping phase for level $i$ is at most $2(1-p_1)\epsilon^2/k$.
Since there are $O(k/\epsilon)$ levels, the total increase in cost
due to these operations for all levels is
$O((1-p_1)\epsilon)$.
By Lemma~\ref{lb}, this is $O(\epsilon)$ times the original
cost of the code.
%END NEY

\iffalse

%(in the analysis we will call this the {\em grouping} phase). 
Let $n_j$ be the cardinality of the $j$th group.
Levels $0$ through $i-1$ contain a total of $n_1+\cdots +n_p$ codewords,
for some integer $p$. Let $x$ be the number of
codewords in level $i$, and let $q$ be such that  
 $n_{p+1}+\cdots +n_q\leq x < n_{p+1}+\cdots + n_{q+1}$. 
We then modify $c$ by taking, in level $i$,
the $x-(n_{p+1}+\cdots + n_{q})$ codewords from group $q+1$, and padding
them with an $a$ to move them out of level $i$. 
Finally, we reorder the assignment of codewords
in levels $>i$ to keep the code ordered
(this does not increase the cost).
Then $c$ is still maximal
within level $i$, and now contains codewords for all elements
of the groups $p+1,
\ldots ,q$, and no element of any other group.

When this construction has been done for every $i$, we obtain a leveled code 
$c'$ that maps elements within each group to the same level. 

\medskip

What is the cost of code $c'$ ?

We examine the increase in cost level by level.  Let 
$t = n_1+\cdots+n_p$ be the total number of codewords
contained within levels $0$ through $i-1$, just before dealing with level $i$.

In the leveling phase for level $i$, 
codewords  in levels $\leq i-1$ are not changed, while codewords within
level $i$  stay in level $i$ so their cost never changes by more than $\epsilon$.
Suppose that
after the leveling phase level
$i$ contains $\delta$ codewords.  Then   $\cost{c}$ has increased by at most 
$\epsilon \left(p_{t+1}+\cdots+p_{t+\delta}\right).$

Let $\delta' = t + n_{p+1}+\cdots +n_q.$ In the grouping phase
for level $i$,  the codewords
$t+1,\ldots,t + \delta'$ are kept on level $i$  while
the codewords $t + \delta' +1,\ldots {t +\delta}$ are padded with an $a.$
The cost added by the padding is at most
$\ell_1 \left(p_{t+\delta'+1}+\cdots+p_{t+\delta}\right)
< (1+\epsilon){(1-p_1)\epsilon^2/ k}$ since $\ell_1\leq 1+\epsilon$, 
the grouping phase does not move  groups of  one word,
and groups of more than one word have total probability 
$\le {(1-p_1)\epsilon^2/ k}.$

Let $P_m$ be the  sum of all of the probabilities of words
in the $m$th group. 
The total cost increase due to the leveling and grouping at level $i$
 is  at most
\begin{eqnarray*}
\lefteqn{\epsilon \sum_{m=p+1}^q P_m + 
(2\epsilon +1) \sum_{j=t+\delta'+1}^{t+\delta} p_j}
\\
& \le &\epsilon \sum_{m=p+1}^q P_m + 
{{(1 +\epsilon) (1-p_1)}\epsilon^2\over k}.
\end{eqnarray*}
We now sum over all $(k-1)/\epsilon$ levels. The second term sums to
$(1+\epsilon )(1-p_1)\epsilon=O(\epsilon OPT)$ by Lemma~\ref{lb}.
The first term sums to either $\epsilon (1-p_1)$ or to $\epsilon$, depending
on whether $c$ maps the first word to level $0$ or to a level $\geq 1$.
In either case this is $O(\epsilon \cost{c})$.
\fi

\end{proof}

Together with Lemma~\ref{lemma:construct}, Lemma~\ref{lemma:existence}
implies that at the end of Step~\ref{step:best},
Algorithm~\ref{alg:main} finds a $k$-prefix code
that has cost at most $(1+O(\epsilon))OPT$.
Lemma~\ref{lemma:convert} implies that, for
$k$ chosen as in Step~\ref{step:init}, the main algorithm
converts the $k$-prefix code into a prefix code that
also has cost at most $(1+O(\epsilon)) OPT$.
This concludes the proof of the performance guarantee
in Theorem~\ref{main_theorem}
for the case $\ell_1>\epsilon/n$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Analysis of running time}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

We analyze the directed graph $D$ which was built
in Step~\ref{step:graph} of Algorithm~\ref{alg:main} and used by 
Algorithm~\ref{alg:construct}.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{Lemma}\label{lem:size_D}
Graph $D$ has at most $nk/\epsilon$ nodes and 
$dnk/\epsilon$
edges, where  $d$ is the
number of distinct letter costs among $\{ \ell_1,\ldots ,\ell_r \}$.
\end{Lemma}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{proof}
From Step~\ref{step:round} of Algorithm~\ref{alg:main} 
all letter costs other than $\ell_1$ are multiples of
$\epsilon$, and $\ell_1$ is either a multiple of $\epsilon$
or evenly divides $\epsilon$.
Moreover, we've assumed $\ell_1>\epsilon /n$.
Thus each of the $k/\epsilon$ levels has at most $n$ distinct costs.
Thus $D$ has at most $nk/\epsilon$ nodes; each node
has outdegree at most $d$, the number of distinct letter costs. 
\end{proof}

In particular, in Step~\ref{step:graph} of Algorithm~\ref{alg:main}
graph $D$ can be constructed in time $O(ndk/\epsilon)$.
Using an array with a bucket for each possible
codeword cost, we can access the nodes of $D$ in constant
time.

%%%%%%%%%%%%%%%%%%%%%%%%
\begin{Lemma}
\label{complexity1}
Algorithm~\ref{alg:construct} can
be implemented to run in time $O(nd k/\epsilon)$.
\end{Lemma}
%%%%%%%%%%%%%%%%%%%%%%%%

\begin{proof}
Since $\ell_1 > \epsilon/n$, there are $O(n/\epsilon)$ nodes
on level 0,
so Step~\ref{line:f(0)} of Algorithm~\ref{alg:construct}
takes time $O(n/\epsilon)$.

The loop of Step~\ref{line:for} is iterated $k/\epsilon$
times. The total time for Step~\ref{line:4}, is at most $O(1)$
per edge, therefore at most $d nk/\epsilon$ total.

Total time for Step~\ref{line:5} is $O(n)$ ($O(1)$ per codeword).
(The exact cost of each iteration depends
on details of implementation of the codeword set $S$. We use an implicit
representation of $S$ by a tree,  and we highlight an edge $e$ of $D$ 
and give it a ``codeword weight'' $w(e)$ if it is used to build
$w(e)$ codewords of $S$. This data structure can be used to obtain
the desired time bounds.)

Finally, Step~\ref{line:7} is implemented by doing a
breadth-first search to extend $D$ beyond cost $k$, starting from
all the nodes of $D$ which have $v_S(\ell)\geq 1$. Since the outdegree
of any node is bounded by $d$, and we stop as soon as we have
identified at most $n$ shortest eligible strings of cost $\geq k$, this has
complexity $O(nd)$.

Overall, the algorithm thus has running time $O(nd k /\epsilon)$.
\end{proof}

{\bf Remark:} Constructing
an explicit representation of $S$ would
require, in general, complexity $\Omega(n^2)$, 
since the optimal codewords can have total
length $\Omega(n^2)$ (for example,
if $S=\{ b,ab,a^2b,\ldots ,a^nb \}$,
as might be the case when $\ell_1\ll 1$).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{Lemma}\label{ref:convert_running_time}
  Algorithm~\ref{alg:convert} can be implemented in time $O(n)$.
\end{Lemma}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{proof} (sketch)
  First represent $S$ with a tree as in the usual
  Huffman encoding problem, compacting the representation as you go
  so that every internal node has at least two children, and so
  the total number of nodes is $O(n)$. Then
  calculate the number of $b$'s recursively in time $O(n)$. Finally,
  modify the tree to insert the extra letters. This can be implemented
  in time $O(n)$.
\end{proof}

We now go back to Algorithm~\ref{alg:main}.
It is easy to see that everything outside Step~\ref{step:for} 
takes time $O(nd)$. From
Lemma~\ref{grouping}, there are only $O(k/\epsilon^2)$ groups, 
and $O(k/\epsilon)$ levels.
Since the assignment of groups to levels respects the ordering
of both, the map is determined by knowing, for each level, the maximum index
of any group assigned to it.
Thus there are $\exp(O(\ln(k/\epsilon) k/\epsilon))$ maps from groups to levels, hence 
$\exp(O(\ln(k/\epsilon) k/\epsilon))$ choices for $(f(1),\ldots, f(k/\epsilon))$.

How about $f(0)$: how many possibilities must we try?
As written,
the algorithm tries every possibility in level $0$, which could
mean as many as $\Theta(n)$, however it is easy to modify the
algorithm so that  we only try $O(\log(n)/\epsilon)$ possibilities for
$f(0)$: indeed,  rounding costs up to the nearest
power of $(1+\epsilon)$, it is enough to try
$f(0)=0,1,\ldots, 1/\epsilon, (1/\epsilon) (1+\epsilon),(1/\epsilon) (1+\epsilon )^2,\ldots ,1$.

Since each iteration takes time $O(ndk/\epsilon)$, 
and there are
$\exp[O(\ln(k/\epsilon) k/\epsilon)]\log(n)/\epsilon$ iterations,
we obtain a complexity of
$(nd\log(n)/\epsilon^2)\exp(O(\ln(k/\epsilon) k/\epsilon))$.
Expanding $k$ and simplifying, this is
$nd\log(n)\exp(O(\ln(1/\epsilon)^2 /\epsilon^2))$.
This completes the proof of Theorem~\ref{main_theorem}
for the case $\ell_1>\epsilon/n$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Dealing with the case $\ell_1\leq\epsilon/n$}\label{sec:l1_tiny}

%NEY rewrote this
Recall that $a$ is the shortest letter and $b$ the second shortest letter,
of cost $\ell_2=1$.  
\begin{Lemma}\label{special_case}
  If $\ell_1 \le \epsilon/n$, then there exists a prefix code
  $c$ with the following properties.
  The cost of $c$ is at most $1+\epsilon$ times the minimum cost of any prefix
  code.   There is a unique codeword of the form $a^{i_0}$ where
  $i_0$ is of the form $\lfloor (1+\epsilon)^j \rfloor$ with $j = O(\log(n)/\epsilon)$.
  Every other codeword has one of the following forms:
  \begin{enumerate}
  \item $ba^j b$ for some $j\le n$, 
  \item $a^j x a^n$ where  $x\in\Sigma-a$ and $j < i_0$.
  \end{enumerate}
\end{Lemma}
\begin{proof}
  Given a minimum-cost prefix code, let $i_0$ be such that
  $a^{i_0}$ is the unique codeword in $a^*$.  Modify the code as follows.

  1. Replace codeword $a^{i_0}$ by $a^{i_1}$, where $i_1$ is
  the next largest integer of the form $\lfloor (1+\epsilon)^j \rfloor$.

  2. For each $i$ ($1\le i\le n$),
  if the $i$th codeword has two or more occurrences of letters
  other than $a$, replace the codeword by $ba^ib$.

  3. Any codeword not modified in Step 1 or 2 must be of the form
  $a^j x a^*$ where $x\in\Sigma-a$ and $0 \le j < i_0$.
  (There can be at most one such starting with $a^j x$.)
  Replace it by $a^j x a^n$.

  This gives a prefix code of the desired form.  It is easy to
  verify that the cost of each codeword is increased by at
  most a $1+\epsilon$ factor.
\end{proof}

The algorithm will first find the minimum-cost code among those of the form
described in Lemma~\ref{special_case} as follows: for each of the
$O(\log(n)/\epsilon)$ choices for $i_0$, consider the ordered code whose
codewords are the $n$ least costly strings in the set
\[\{a^{i_0}\}\cup \{ba^jb: j < n\}\cup  \{a^jx a^n: j < i_0\}.\]
Among the codes considered, take the one of minimum cost.
By the lemma, the cost of this code will by at most
$1+\epsilon$ times the minimum cost of any prefix code.

Under Assumption~\ref{assumptions},
each iteration can be implemented in $O(n+d)=O(n)$ time,
so for this special case the algorithm takes 
$O(n\log(n)/\epsilon)$ time.
%NEY end

\iffalse
Recall that $a$ is the shortest letter and $b$ the second shortest letter,
of cost $\ell_2=1$. First notice that if $b$ is a codeword, then replacing
$b$ by $ba^n$ only increases the cost by a factor of $1+\epsilon$.
Next, notice that one can always add to the
code the strings $bb$, $bab$, $ba^2b$, $\ldots$, $ba^{n-1}b$ (removing any codewords which
have those as a prefix).
It is now straightforward to design an algorithm. Let $\Sigma'\subset\Sigma$
denote the letters of $\Sigma\setminus\{ a,b\}$ whose cost are less than 2.

For each guess $f(0)\in \{ 1,(1+\epsilon),(1+\epsilon)^2,\ldots,n \}$, build a code in a greedy manner
by taking the following strings  as codewords one by one in increasing
order of cost until you have $n$ codewords:
\begin{itemize}
\item 
$a^{f(0)}$
\item
$ba^n,aba^n,a^2ba^n,\ldots ,a^{f(0)-1}ba^n$
\item
for each $\sigma\in \Sigma'$ by order of increasing cost of $\sigma$, take
$\sigma ,a\sigma, a^2\sigma ,\ldots ,a^{f(0)-1}\sigma$
\item
$bb,bab,ba^2b,\ldots ,ba^{n-1}b$.
\end{itemize}
The observations at the beginning of this section imply that the code
built by the greedy construction  
is within $1+ \eps$ of the minimum cost code that contains
$a^{f(0)}.$
Outputting the best code among the codes thus constructed therefore 
outputs a code within $(1 + \epsilon) OPT$.

The greedy construction can be implemented in $O(n+d)$ time;
constructing all $n$ such codes corresponding to the different
choices of $a(0)$ can therefore be done in $O(\log(n)(n+d)/\epsilon)$ time.
\fi

\bibliographystyle{plain}
\bibliography{ptas}
\end{document}

STOC_Final.bbl
\begin{thebibliography}{10}

\bibitem{LEC-73}
Shimon~Even Abraham~Lempel and Martin Cohen.
\newblock An algorithm for optimal prefix parsing of a noiseless and memoryless
  channel.
\newblock {\em IEEE Transactions on Information Theory}, 19(2):208--214, March
  1973.

\bibitem{Abrahams-01}
Julia Abrahams.
\newblock Code and parse trees for lossless source encoding.
\newblock {\em Communications in Information and Systems}, 1(2):113--146, April
  2001.

\bibitem{AM-80}
Doris Altenkamp and Kurt Melhorn.
\newblock Codes: Unequal probabilies, unequal letter costs.
\newblock {\em Journal of the Association for Computing Machinery},
  27(3):412--427, July 1980.

\bibitem{BY-90}
Toby Berger and Raymond~W. Yeung.
\newblock Optimum $1$-ended binary prefix codes.
\newblock {\em IEEE Transactions on Information Theory}, 36(6):1434--1441,
  November 1990.

\bibitem{Blach-54}
N.~M. Blachman.
\newblock Minimum cost coding of information.
\newblock {\em IRE Transactions on Information Theory}, PGIT-3:139--149, 1954.

\bibitem{CG-96}
Siu-Ngan Choi and M.~Golin.
\newblock Lopsided trees: Algorithms, analyses and applications.
\newblock In {\em Proc. of the 23rd International Colloquium on Automata
  Languages and Programming (ICALP '96)}, pages 538--549, 1996.

\bibitem{Cot-75}
N.~Cot.
\newblock Complexity of the variable-length encoding problem.
\newblock In {\em Proc. 6th Southeast Conference on Combinatorics, Graph Theory
  and Computing}, pages 211--244, 1975.

\bibitem{Cot-77}
Norbert Cott.
\newblock {\em Characterization and Design of Optimal Prefix Codes}.
\newblock PhD Thesis, Stanford University, Department of Computer Science, June
  1957.

\bibitem{Csiszar-69}
I.~Csisz'ar.
\newblock Simple proofs of some theorems on noiseless channels.
\newblock {\em Inform. Contr.}, 514:285--298, 1969.

\bibitem{gilb-69}
E.~N. Gilbert.
\newblock How good is morse code.
\newblock {\em Inform Control}, 14:585--565, 1969.

\bibitem{gilb-95}
E.~N. Gilbert.
\newblock Coding with digits of unequal costs.
\newblock {\em IEEE Trans. Inform. Theory}, 41:596--600, 1995.

\bibitem{GR-98}
M.~Golin and G.~Rote.
\newblock A dynamic programming algorithm for constructing optimal prefix-free
  codes for unequal letter costs.
\newblock {\em IEEE Transactions on Information Theory}, 44(5):1770--1781,
  1998.

\bibitem{GY-94}
M.~Golin and N.~Young.
\newblock Prefix codes: Equiprobable words, unequal letter costs.
\newblock {\em SIAM Journal on Computing}, 25(6):1281--1292, December 1996.

\bibitem{Hind-90}
K.~Hinderer.
\newblock On dichotomous search with direction-dependent costs for a uniformly
  hidden objec.
\newblock {\em Optimization}, 21(2):215--229, 1990.

\bibitem{Huff-52}
D.~A. Huffman.
\newblock A method for the construction of minimum redundancy codes.
\newblock In {\em Proc. IRE 40}, volume~10, pages 1098--1101, September 1952.

\bibitem{Imm-99}
K.~A.~S. Immink.
\newblock {\em Codes for Mass Data Storage Systems}.
\newblock Shannon Foundations Publishers, 1999.

\bibitem{Itai-76}
I.~Itai.
\newblock Optimal alphabetic trees.
\newblock {\em SIAM J. Computing}, 5:9--18, 1976.

\bibitem{kr-89}
Sanjiv Kapoor and Edward~M. Reingold.
\newblock Optimum lopsided binary trees.
\newblock {\em Journal of the Association for Computing Machinery},
  36(3):573--590, July 1989.

\bibitem{Karp-61}
Richard Karp.
\newblock Minimum-redundancy coding for the discrete noiseless channel.
\newblock {\em IRE Transactions on Information Theory}, IT-7:27--39, January
  1961.

\bibitem{Knuth-73}
Donald~E. Knuth.
\newblock {\em The Art of Computer Programming, Volume III: Sorting and
  Searching}.
\newblock Addison-Wesley, 1973.

\bibitem{Krause-62}
R.~M. Krause.
\newblock Channels which transmit letters of unequal duration.
\newblock {\em Inform. Contr.}, 5:13--24, 1962.

\bibitem{Marcus-57}
R.S. Marcus.
\newblock {\em Discrete Noiseless Coding}.
\newblock M.S. Thesis, MIT E.E. Dept, 1957.

\bibitem{Mehlhorn-80}
K.~Mehlhorn.
\newblock An efficient algorithm for constructing nearly optimal prefix codes.
\newblock {\em IEEE Trans. Inform. Theory}, 26:513--517, September 1980.

\bibitem{BGLR-98}
L.~L.~Larmore P.~Bradford, M.~Golin and W.~Rytter.
\newblock Optimal prefix-free codes for unequal letter costs and dynamic
  programming with the monge property.
\newblock In {\em Proc. Sixth European Symposium on Algorithms (ESA'98) (LNCS
  1461)}, pages 43--54, 1998.

\bibitem{PGE-75}
Y.~Perl, M.~R. Garey, and S.~Even.
\newblock Efficient generation of optimal prefix code: Equiprobable words using
  unequal cost letters.
\newblock {\em Journal of the Association for Computing Machinery},
  22(2):202--214, April 1975.

\bibitem{CSP-94}
A.~De~Santis R.~M.~Capocelli and G.~Persiano.
\newblock Binary prefix codes ending in a $1$.
\newblock {\em IEEE Transactions on Information Theory}, 40(4):1296--1302, July
  1994.

\bibitem{DKY-99}
E.~Korach S.~Dolev and D.~Yukelson.
\newblock The sound of silence: Guessing games for saving energy in mobile
  environment.
\newblock In {\em Proc. of the Eighteenth Annual Joint Conference of IEEE
  Computer and Communications Societies (IEEE INFOCOM'99)}, pages 768--775,
  1995.

\bibitem{Stan-70}
L.~E. Stanfel.
\newblock Tree structures for optimal searching.
\newblock {\em Journal of the Association for Computing Machinery},
  17(3):508--517, July 1970.

\bibitem{Varn-71}
B.~Varn.
\newblock Optimal variable length codes (arbitrary symbol cost and equal code
  word probability).
\newblock {\em Information Control}, 19:289--301, 1971.

\end{thebibliography}
