Doctoral Dissertations

Date of Award

12-1982

Degree Type

Dissertation

Degree Name

Doctor of Philosophy

Major

Management Science

Major Professor

Robert S. Garfinkel

Committee Members

Kenneth Gilbert, John Philpot, Robert Woodruff

Abstract

The initial theoretical development in the area of Error Localization for purposes of data imputation in validating records which fail specified consistency conditions is due to Fellegi and Holt. Garfinkel and Liepins proposed two different procedures for solving the Minimum Weighted Fields to Impute problem (MWFI) associated with failing data records which contain categorical data only. The formal development of theory leading to these procedures and a comparative computational analysis of these two procedures forms a part of this work. Recognizing that the Minimum Fields to Impute problem with Continuous data records (MWFIC) is a special case of the general fixed charge problem and is closely related to the Cardinality Constraint Linear Programming problem (CCLP) the use of an extreme point enumeration algorithm such as one due Chernikova for solving MWFIC was suggested by Sande. Motivated by Rubin's adaptation of the Chernikova algorithm for solving CCLP's two extreme point (implicit) enumeration algorithms are proposed in this work for solving MWFIC and MFIC and the theory leading to the specification of these algorithms is carefully developed.

A cutting plane algorithm motivated by Garfinkel's algorithm solving for MWFI and similar in spirit to it is proposed for solving MWFIC. The theory leading to the specification of this algorithm and computational experience with it are also presented. For purposes of solving larger MWFIC problems than can be solved by any of the existing algorithms a heuristic algorithm is proposed. A comparative analysis of the computational performance of the heuristic versus the cutting plane algorithm for solving MWFIC is also presented.

Download
Files over 3MB may be slow to open. For best results, right-click and select "save as..."

Share

COinS