A linear time randomizing algorithm for searching ranked functions (Q1101237)

Consider a set F of n functions defined on a common interval U. A ranked function over F is defined from the functions of F by using order information such as the k largest function, the sum of k largest functions, etc. We give a linear time randomizing algorithmic paradigm for finding local roots, optima, intersection points, etc., of ranked functions. The algorithm is generalized to the cost effective resource allocation problem and to various variants of the parametric knapsack problem.