|
Activity Number:
|
475
|
|
Type:
|
Contributed
|
|
Date/Time:
|
Thursday, August 7, 2003 : 10:30 AM to 12:20 PM
|
|
Sponsor:
|
Section on Statistical Computing
|
| Abstract - #300839 |
|
Title:
|
Preorder and Set Covering in the DISCRETE Edit System
|
|
Author(s):
|
Bor-Chung Chen*+ and William E. Winkler
|
|
Companies:
|
U.S. Census Bureau and U.S. Census Bureau
|
|
Address:
|
4700 Silver Hill Rd., Washington, DC, 20233-9100,
|
|
Keywords:
|
integer programming ; optimization ; lexicographic ordering ; minimal change ordering ; ranking ; unranking
|
|
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 imperative. The DISCRETE edit system, based on the Fellegi and Holt model (1976) of editing, contains combinatorial problems. One is the set covering problem (SCP). The SCP is formulated many times in the two major components of the DISCRETE edit system: edit generation and error localization. Therefore, an efficient set covering algorithm is critical to the overall performance of the 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. We will describe a simple implementation of the preorder of traversing a tree used in a new set covering algorithm proposed by Chen (1998). The implementation eliminates the storage requirements of the preorder tree while maintaining the efficiency of the algorithm. The storage size required is 2 to the power of n, where n is the number of nodes in the preorder tree, that is very large when n is big and has been eliminated in the proposed implementation.
|
