Approximation Algorithms for Linear Fractional-Multiplicative Problems

Daniele Depetrini (depetrinilibero.it)
Marco Locatelli (locatelldi.unito.it)

Abstract: In this paper we propose a Fully Polynomial Time Approximation Scheme (FPTAS) for a class of optimization problems where the feasible region is a polyhedral one and the objective function is the sum or product of linear ratio functions. The class includes the well known ones of Linear (Sum-of-Ratios) Fractional Programming and Multiplicative Programming.

Keywords: Fractional Programming, Multiplicative Programming, Approximation Problems

Category 1: Global Optimization (Theory )

Citation:

Download: [PDF]

Entry Submitted: 12/14/2007
Entry Accepted: 12/19/2007
Entry Last Modified: 01/09/2008

Modify/Update this entry