Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
9663986 | European Journal of Operational Research | 2005 | 20 Pages |
Abstract
This paper deals with optimization of functions that depend on (large-scale) data via a linear transformation of rank two. An algorithm is presented which--under mild assumptions--finds the global solution with polynomial-time complexity in the worst case, provided the critical points of the objective can be controlled with the same effort. Moreover, for important subclasses of objectives including the linear-fractional, and the quadratic case, we arrive at a linear-time algorithm. For both cases, small simulation studies are provided to illustrate the average case runtime behaviour. As a possible application, sensitivity of cost assessment in communication networks is addressed where the problems may have tens of thousands of variables.
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Immanuel M. Bomze,