National Statistics Institute

Methods and projects / Working papers

Methods and Projects
Portada documentos de trabajo

Two greedy algorithms for a binary quadratically constrained linear program in survey data editing

Doc: 03/2012

We propose a binary quadratically constrained linear program as an approach to selective editing. In a practice-oriented framework and allowing for some overediting whilst strictly fulfilling accuracy restrictions, we propose two greedy algorithms to find feasible suboptimal solutions. Their running times are quartic and cubic, respectively, in the number of sampling units and linear in the number of restrictions. We present computational evidence from several hundreds of instances randomly generated.

Palabras clave / Key words: Combinatorial optimization, quadratic constraint, linear program, greedy algorithm, selective editing.

Two greedy algorithms for a binary quadratically constrained linear program in survey data editing (Pdf 230 KB)
David Salgado, Ignacio Arbués, María Elisa Esteban