An O(n) Algorithm for Projecting a Vector on the Intersection of a Hyperplane and a Box in ℝn1 , 2


    loading  Checking for direct PDF access through Ovid

Abstract

We consider the problem of projecting a vector on the intersection of a hyperplane and a box in ℝn. This paper extends a previous result of Maculan, Minoux, and Plateau (Ref. 1) concerning the projection of a vector on the intersection of a hyperplane and ℝn+. We present an O(n) time algorithm based on the linear-time median-finding algorithm. This algorithm determines the median of the components of the vector to be projected. Computational results are also presented in order to evaluate the algorithm and its time complexity. We consider two sets of instances which are randomly generated for any given n. The algorithm was successful in solving all the instances in a reasonable time.

    loading  Loading Related Articles