CHEN Danny Z, DAESCU Ovidiu, DAI Yang, KATOH Naoki, WU Xiaodong, XU Jinhui
IPSJ SIG Notes, 2000(31) 25-32, Mar 21, 2000
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 ratio query (OLRQ) problem, which computer 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.