Given a data set defined by n samples, the Data set Reconstruction Problem (DRP) consists in determining a subset of samples with prefixed cardinality that minimizes the reconstruction error of the whole data set. This problem has several practical applications, e.g., those arising in the biomedical field as Electrocardiography data acquisition and X-ray Computed Tomography examinations. In this paper, we propose both exact and heuristic algorithms for DRP based on dynamic programming. Computational experiments on a large set of both real-world and randomly generated instances of DRP are discussed, showing the effectiveness of the proposed approaches.
