The Moore-Penrose Pseudoinverse (MPP) is a key tool in data analysis. Eg., it can be used to solve least-squares problems. But the MPP is typically dense, and with very large data sets, we may be content with an approximation of MPP that is much sparser. When we have a use case where we need to multiply many vectors by the MPP, we may be willing to put in substantial effort to get a sparse approximation. We use linear programming and (not) semidefinite programming to define and calculate various sparse generalized inverses, and we use a local-search scheme to derive a relevant polynomial-time approximation algorithm. This is joint work with Marcia Fampa (UFRJ) and Victor Fuentes (UM).