DannyZ.Chen, Ovidiu Daescu, 戴陽, 加藤 直樹, Xiaodong Wu, Jinhui Xu
情報処理学会研究報告アルゴリズム(AL) 2000(31) 25-32 2000年3月21日
n個の線形制約の下でd変数のm個の線形分数関数の和を最大化する問題を考察する。とくにd=2に対して従来のアルゴリズムを改良する。その改良の鍵となる部分問題は動的に変化する制約条件下のパラメトリック最適化問題であり,これをO((m+n)log(m+n))時間で効率的に解くアルゴリズムを開発した。計算実験の結果,従来のアルゴリズムに比べて計算時間がかなり改良されたことを検証した。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 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.