Exact parallel algorithms for the location depth and maximum feasible subsystems
Vera Rosta, Department of Mathematics and Statistics, McGill University

Abstract : Given a system of linear inequalities, consider the problem of finding a maximum feasible subsystem, that is to compute a solution satisfying as many inequalities as possible. This general problem, called MAX FLS, was shown to be NP-complete. Deterministic algorithms for this or related problems were only available in 2 or 3 dimensions. To compute MAX FLS we consider its combinatorial formulation and present an algorithm in any dimension which is memory efficient and highly parallelizable. We also propose an algorithm for computing multidimensional generalization of ranks in higher dimensions for non-parametric statistics or equivalently computing the location of a point relative to a given multidimensional point set in any non-fixed dimension for computational or convex geometry. This can be considered as a first attempt to compute exactly non-parametric statistical data depth measures in higher dimensions.


Announcement Poster in PDF