Optimizing the sum of linear fractional functions and applications

The problem of optimizing the sum of m linear fractional functions (SOLF) in a fixed dimension d, subject to n linear constraints, arises in a number of theoretical and applied areas. This paper presents an improved algorithm for solving the SOLF problem in 2-D. A key subproblem to our solution is the off-line radio query (OLRQ) problem, which computes the optimal values of a sequence of m linear fractional functions (called ratios), with the ratios subject to a dynamically changing feasible domain defined by O(n) linear constraints. Based on useful geometric properties and the parametric linear programming technique, we develop an algorithm that solves the 2-D OLRQ problem in O((m+n)log(m+n)) time. Our OLRQ algorithm can be easily implemented and is robust. More importantly, it enables us to speed up every iteration of a known iterative SOLF algorithm in 2-D, from O(m(m+n)) time to O((m+n)log(m+n)). Implementation results of our improved SOLF algorithm have shown that in most cases our algorithm outperforms the commonly-used approaches for the SOLF problem. We also show that several geometric optimization problems can be formulated as 2-D SOLF problems, and hence are solvable by our algorithm.