Efficient Algorithms and Implementations for Optimizing the Sum of Linear Fractional Functions, with Applications

Danny Z. Chen (), Ovidiu Daescu (), Yang Dai (), Naoki Katoh (), Xiaodong Wu () and Jinhui Xu ()
Additional contact information
Danny Z. Chen: University of Notre Dame
Ovidiu Daescu: University of Texas at Dallas
Yang Dai: University of Illinois at Chicago
Naoki Katoh: Kyoto University Katsura
Xiaodong Wu: University of Texas-Pan American
Jinhui Xu: State University of New York at Buffalo

Journal of Combinatorial Optimization, 2005, vol. 9, issue 1, No 6, 69-90

Abstract: Abstract This paper presents an improved algorithm for solving the sum of linear fractional functions (SOLF) problem in 1-D and 2-D. A key subproblem to our solution is the off-line ratio query (OLRQ) problem, which asks to find the optimal values of a sequence of m linear fractional functions (called ratios), each ratio subject to a feasible domain defined by O(n) linear constraints. Based on some geometric properties and the parametric linear programming technique, we develop an algorithm that solves the OLRQ problem in O((m+n)log (m+n)) time. The OLRQ algorithm can be used to speed up every iteration of a known iterative SOLF algorithm, from O(m(m+n)) time to O((m+n)log (m+n)), in 1-D and 2-D. Implementation results of our improved 1-D and 2-D SOLF algorithm have shown that in most cases it outperforms the commonly-used approaches for the SOLF problem. We also apply our techniques to some problems in computational geometry and other areas, improving the previous results.

Keywords: combinatorial optimization; computational geometry; sum of linear fractional functions; parametric linear programming; robustness (search for similar items in EconPapers)
Date: 2005
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-005-5485-2 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:9:y:2005:i:1:d:10.1007_s10878-005-5485-2

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-005-5485-2

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().