Alphabetic coding with exponential costs

This note considers an alphabetic binary tree formulation in a family of nonlinear problems. An application of this family occurs when a random outcome needs to be determined via alphabetically ordered search within a stochastic time window. Rather than finding a decision tree minimizing , this variant involves minimizing for a given a∈(0,1). Herein a dynamic programming algorithm finds the optimal solution in O(n3) time and O(n2) space; methods traditionally used to improve the speed of optimizations in related problems, such as the Hu–Tucker procedure, fail for this problem. This note thus also introduces two algorithms which can find a suboptimal solution in linear time (for one) or O(nlogn) time (for the other), with associated redundancy bounds guaranteeing their coding efficiency.