A data correcting (DC) algorithm is a branch-and-bound-type algorithm, in which the data of a given problem is “heuristically corrected” at the various stages in such a way that the new instance will be polynomially solvable and its optimal solution is within a prespecified deviation (called prescribed accuracy) from the optimal solution to the original problem. The DC approach is applied to determining exact and approximate global optima of NP-hard problems. DC algorithms are designed for various classes of NP-hard problems including the Asymmetric Traveling Salesman (ATSP), Simple Plant Location (SPLP), Quadratic Cost Partition (QCP), p-Median (PMP) problem, and problems based on the algorithmically defined polynomially solvable special cases. Results of computational experiments on the publicly available benchmark instances as well as on random instances are presented. A statement related to a proven model optimality of the p-median problem (PMP) within the class of mixed Boolean Linear Programming models in terms of the numbers of coefficients in the objective function, variables, and constraints is overviewed as well.