Research Reports

Preorder and Set Covering in the DISCRETE Edit System

Bor-Chung Chen and William E. Winkler

KEY WORDS:Redundant Covers, Subcovers, Integer Programming, Optimization, Lexicographic Ordering, Minimal Change Ordering, Ranking, Unranking, Successor

ABSTRACT

Most combinatorial problems are very big - bigger than what can be handled efficiently on most fast computers - and hence the development and implementation of fast algorithms is very important. The DISCRETE edit system, based on the Fellegi and Holt model (1976) of editing, contains a combinatorial problem: the set covering problem (SCP). The two major components of the edit system are edit generation and error localization. The SCP is formulated many times in both components. Therefore, an efficient set covering algorithm is critical to the overall performance of the DISCRETE edit system. The preorder of traversing a tree is one of the structures used in the design of a set covering algorithm for the DISCRETE edit system. In this paper, we will describe a simple implementation of the preorder of traversing a tree used in a new set covering algorithm proposed by Chen (1998).

Source: U.S. Census Bureau, Statistical Research Division

Created: 10-SEP-2003