Harvard University

Abstract:  The compact and harmonious layout of ads and text is a fundamental and costly step in the production of commercial telephone directories ("Yellow Pages"). We formulate a canonical version of Yellow-Pages pagination and layout (YPPL) as an optimization problem in which the task is to position ads and text-stream segments on sequential pages so as to minimize total page length and maximize certain layout aesthetics, subject to cons~aints derived from page-format requirements and positional relations between ads and text. We present a heuristic-search approach to the YPPL problem. Our algorithm has been applied to a sample of real telephone-directory data, and produces solutions that are significantly shorter and better than the published ones. Key Words: directory pagination, page layout, heuristic search, stochastic optimization, simulated annealing 1. I n t r o d u c t i o n The problem of Yellow-Pages (YP) pagination and layout (YPPL) is one of finding a com-pact and harmonious positioning of text and advertisements on the pages of a commercial telephone directory. Figure 1 depicts a sample page from a commercial Yellow Pages directory. We use this figure to define some useful terminology. Regular ads, which can span more than one