A linear time randomizing algorithm for searching ranked functions

Consider a setF ofn functions defined on a common intervalU. A ranked function overF is defined from the functions ofF by using order information such as thek largest function, the sum ofk 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.Part of this work was done when the author was visiting Tel Aviv University.Supported, in part, by NSF Grant ECS-812141, and by the Mia Fischer David Foundation through the Israel Institute of Business Research, Tel Aviv University. IIBR working papers are intended for preliminary circulation of tentative research results. Comments are welcome and should be addressed directly to the author.