Abstract
In this paper we propose a Fully Polynomial Time Approximation Scheme for a class of optimization problems where the feasible region is a polyhedral one and the objective function is the sum or product of ratios of linear functions. The class includes the well known ones of Linear (Sum-of-Ratios) Fractional Programming and Multiplicative Programming.
Similar content being viewed by others
References
Depetrini, D., Locatelli, M.: A FPTAS for a class of linear multiplicative problems. To appear in Comput. Optimi. Appl. doi:10.1007/s10589-007-9156-3
Depetrini, D., Locatelli, M.: Approximation algorithms for linear fractional-multiplicative problems, http://www.optimization-online.org/DB_HTML/2007/12/1860.html
Kern W., Woeginger G.: Quadratic programming and combinatorial minimum weight product problems. Math. Program. 110, 641–649 (2007)
Konno H., Kuno T.: Multiplicative programming problems. In: Horst, R., Pardalos, P.M. (eds) Handbook of Global Optimization, pp. 369–405. Kluwer, Dordrecht (1995)
Matsui T.: NP-hardness of linear multiplicative programming and related problems. J. Glob. Optim. 9, 113–119 (1996)
Nemhauser T., Wolsey L.A.: Integer and Combinatorial Optimization. Wiley, New York (1988)
Schaible S., Ibaraki T.: Fractional programming. European J. Oper. Res. 12, 325–338 (1983)
Schaible S., Shi J.: Fractional programming: the sum-of-ratios case. Optim. Methods Softw. 18, 219–229 (2003)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Depetrini, D., Locatelli, M. Approximation of linear fractional-multiplicative problems. Math. Program. 128, 437–443 (2011). https://doi.org/10.1007/s10107-009-0309-2
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10107-009-0309-2