Approximation algorithms for combinatorial fractional programming problems.(English)Zbl 0616.90078
We are concerned with a combinatorial optimization problem which has the ratio of two linear functions as the objective function. This type of problems can be solved by an algorithm that uses an auxiliary problem with a parametrized linear objective function. Because of its combinatorial nature, however, it is often difficult to solve the auxiliary problem exactly. In this paper, we propose an algorithm which assumes that the auxiliary problems are solved only approximately, and prove that it gives an approximate solution to the original problem, of which the accuracy is at least as good as that of approximate solutions to the auxiliary problems. It is also shown that the time complexity is bounded by the square of the computation time of the approximate algorithm for the auxiliary problem. As an example of the proposed algorithm, we present a fully polynomial time approximation scheme for the fractional 0-1 knapsack problem.
MSC:
| 90C32 | Fractional programming |
| 90C27 | Combinatorial optimization |
| 68Q25 | Analysis of algorithms and problem complexity |
| 90C09 | Boolean programming |
Cite
Full Text:DOI
References:
| [1] | G.R. Bitran and T.L. Magnanti, ”Duality and sensitivity analysis for fractional programs,”Operations Research 24 (1976) 675–699. ·Zbl 0361.90073 ·doi:10.1287/opre.24.4.675 |
| [2] | R. Chandrasekaran, ”Minimal ratio spanning trees,”Networks 7 (1977) 335–342. ·Zbl 0366.94044 ·doi:10.1002/net.3230070405 |
| [3] | W. Dinkelbach, ”On nonlinear fractional programming,”Management Science 13 (1976) 492–498. ·Zbl 0152.18402 ·doi:10.1287/mnsc.13.7.492 |
| [4] | B. Fox, ”Finding minimal cost-time ratio circuits,”Operations Research 17 (1969) 546–551. ·doi:10.1287/opre.17.3.546 |
| [5] | G.V. Gens and L.V. Levner, ”Discrete optimization problems and efficient approximate algorithms,”Engineering cybernetics 17 (1979) 1–11. ·Zbl 0457.90054 |
| [6] | P.C. Gilmore and R.E. Gomory, ”A linear programming approach to the cutting stock problems– part II,”Operations Research 11 (1963) 863–888. ·Zbl 0124.36307 ·doi:10.1287/opre.11.6.863 |
| [7] | T. Ibaraki, ”Solving mathematical programming problems with fractional objective functions,” in: S. Schaible and Z.T. Ziemba, eds.,Generalized Concavity in Optimization and Economics (Academic Press, New York, 1981) pp. 441–472. ·Zbl 0534.90088 |
| [8] | T. Ibaraki, ”Parametric approaches to fractional programs,” Mathematical Programming26 (1983) 345–362. ·Zbl 0506.90078 ·doi:10.1007/BF02591871 |
| [9] | H. Ishii, T. Ibaraki and H. Mine, ”Fractional knapsack problems,”Mathematical Programming 13 (1976) 255–271. ·Zbl 0378.90071 ·doi:10.1007/BF01584342 |
| [10] | R. Jagannathan, ”On some properties of programming problems in parametric form pertaining to fractional programming,”Management Science 12 (1966) 609–615. ·Zbl 0143.21602 ·doi:10.1287/mnsc.12.7.609 |
| [11] | N. Megiddo, ”Combinatorial optimization with rational objective functions,”Mathematics of Operations Research 4 (1979) 414–424. ·Zbl 0425.90076 ·doi:10.1287/moor.4.4.414 |
| [12] | C.H. Papadimitriou and K. Steiglitz,Combinatorial Optimization: Algorithms and Complexity (Prentice-Hall, Englewood Cliffs, NJ, 1982). ·Zbl 0503.90060 |
| [13] | S. Sahni, ”General techniques for combinatorial approximation,”Operations Research 25 (1977) 920–936. ·Zbl 0386.90048 ·doi:10.1287/opre.25.6.920 |
| [14] | S. Schaible, ”Fractional Programming: Applications and algorithms,”European Journal of Operational Research 7 (1981) 111–120. ·Zbl 0452.90079 ·doi:10.1016/0377-2217(81)90272-1 |
| [15] | S. Schaible, ”Fractional programming,”Zeitschrift für Operations Research 27 (1983) 39–54. ·Zbl 0527.90094 ·doi:10.1007/BF01916898 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
