Set Covering Algorithms in Edit Generation
Bor-Chung Chen, U. S. Bureau · 1998
Results are presented from a comparison study of several set covering algorithms (routines) used in the implicit edit generation algorithms of Garfinkel, Kunnathur, and Liepins [1986] and Winkler [1997]. The edit generation algorithms are based on the Fellegi and Holt model [1976] of editing. Since the set covering routine is called many times in edit generation, an efficient routine will significantly reduce the computing time of the generation process. Unlike most of the applications of the set covering problem (SCP), in which an optimal cover is desirable, the edit generation is interested in finding all the prime covers to a SCP. KEY WORDS: Explicit Edits, Redundant Covers, Subcovers, Integer Programming, Optimization 1. Introduction The information gathered in any survey may contain inconsistent or incorrect data. These erroneous data need to be revised prior to data tabulations and retrieval. The revisions of the erroneous data should not affect the statistical inferences of the...