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

Danny Chen; Ovidiu Daescu; Yang Dai; Naoki Katoh; Xiaodong Wu; Jinhui Xu

doi:10.1007/s10878-005-5485-2

Back

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

Journal article

Peer reviewed

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

Danny Chen, Ovidiu Daescu, Yang Dai, Naoki Katoh, Xiaodong Wu and Jinhui Xu

Journal of combinatorial optimization, Vol.9(1), pp.69-90

02/2005

DOI: 10.1007/s10878-005-5485-2

View Online

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.

combinatorial optimization

sum of linear fractional functions

Convex and Discrete Geometry

computational geometry

robustness

Mathematics

Theory of Computation

Mathematical Modeling and Industrial Mathematics

Operation Research/Decision Theory

Combinatorics

Optimization

parametric linear programming

Details

Title: Subtitle: Efficient Algorithms and Implementations for Optimizing the Sum of Linear Fractional Functions, with Applications
Creators: Danny Chen - Department of Computer Science and Engineering University of Notre Dame Notre Dame IN 46556 USA
Ovidiu Daescu - Department of Computer Science University of Texas at Dallas Richardson TX 75080 USA
Yang Dai - Department of Bioengineering (M/C 063) University of Illinois at Chicago Chicago IL 60607 USA
Naoki Katoh - Department of Architecture and Architectural Systems, Graduate School of Engineering Kyoto University Katsura Nishikyo-ku Kyoto Japan
Xiaodong Wu - Department of Computer Science University of Texas-Pan American 1201 W. University Drive Edinburg TX 78541 USA
Jinhui Xu - Department of Computer Science and Engineering State University of New York at Buffalo Buffalo NY 14260 USA
Resource Type: Journal article
Publication Details: Journal of combinatorial optimization, Vol.9(1), pp.69-90
DOI: 10.1007/s10878-005-5485-2
ISSN: 1382-6905
eISSN: 1573-2886
Publisher: Kluwer Academic Publishers; Boston
Language: English
Date published: 02/2005
Academic Unit: Electrical and Computer Engineering; Radiation Oncology
Record Identifier: 9984047984302771

Metrics

23 Record Views

15 Times Cited - Web of Science