  It is possible to improve upon Tunstall coding using a collection of multiple
parse trees. The best such results so far are Iwata and Yamamoto's maximum cost
AIVF codes. The most efficient algorithm for designing such codes is an
iterative one that could run in exponential time. In this paper, we show that
this problem fits into the framework of a newly developed technique that uses
linear programming with the Ellipsoid method to solve the minimum cost Markov
chain problem. This permits constructing maximum cost AIVF codes in (weakly)
polynomial time.
