Least-cost partition algorithms. (English) Zbl 0679.90088
The authors present three modifications of the standard \(O(n^ 2)\) dynamic programming algorithm for the knapsack problem. The first one restricts the number of possible substitutions, leading to significant average-case complexity improvement; worst-cost complexity remains \(O(n^ 2)\), but average-case complexity becomes \(O(n^{3/2})\). The second is a method of condensing partially developed solutions. The third is a prepass which eliminates some equations and guarantees O(n) or O(n log n) efficiency in a number of important special cases. Also, a related algorithm for the problem of partitioning an integer by integers not larger than some upper bound p, of complexity polynomial in p, is given.
Reviewer: E.Duca
MSC:
| 90C39 | Dynamic programming |
| 68Q25 | Analysis of algorithms and problem complexity |
| 90C10 | Integer programming |
| 05A17 | Combinatorial aspects of partitions of integers |
Keywords:
least-cost partition problem; knapsack problem; average-case complexity; worst-cost complexityReferences:
| [1] | Allen, F. E.; Cocke, J., A program data flow analysis procedure, Comm. ACM, 19, 137-147 (1977) · Zbl 0317.68016 |
| [2] | Bellman, R., Dynamic Programming (1957), Princeton University Press: Princeton University Press Princeton, NJ · Zbl 0077.13605 |
| [3] | Chvatal, V., Linear Programming (1983), Freeman: Freeman New York · Zbl 0318.05002 |
| [4] | Cocke, J., Global common subexpression elimination, (Proceedings ACM SIGPLAN Symposium on Compiler Construction (1970)), 20-24 |
| [5] | Gilmore, P.; Gomory, R., The theory and computation of knapsack functions, Oper. Res., 14, 6, 1045-1074 (1966) · Zbl 0173.21502 |
| [6] | Garfinkel, R.; Nemhauser, G., Integer Programming (1972), Wiley: Wiley New York · Zbl 0259.90022 |
| [7] | Hardy, G. W.; Wright, E. M., An Introduction to the Theory of Numbers (1938), Clarendon: Clarendon Oxford · Zbl 0020.29201 |
| [8] | Hecht, M. S., Flow Analysis of Computer programs (1977), North-Holland: North-Holland Amsterdam · Zbl 0381.68013 |
| [9] | Horowitz, E.; Sahni, S., Fundamentals of Computer Algorithms (1978), Computer Science Press: Computer Science Press Rockville, MD · Zbl 0442.68022 |
| [10] | Ibarra, O.; Kim, C., Fast approximate algorithms for the knapsack and sum of subsets problems, J. ACM, 22, 463-468 (1975) · Zbl 0345.90049 |
| [11] | Knuth, D. E., Optimum binary search trees, Acta, 1, 14-26 (1971) · Zbl 0233.68010 |
| [12] | Knuth, D. E., The Art of Computer Programming, III: Sorting and Searching (1973), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0302.68010 |
| [13] | Lawler, E., Fast approximate algorithms for the knapsack problem, (Proceedings 18th Annual Symposium on the Foundations of Computer Science (1977)), 206-213 |
| [14] | Marlowe, T., A least-cost partition algorithm, (Proceedings Fall Joint Computer Conference (1986)), 637-647 |
| [15] | Marlowe, T.; Paull, M. C., Least-cost partition algorithms, (Tech. Rept. DCS-TR-169 (1986), Department of Computer Science, Rutgers University: Department of Computer Science, Rutgers University New Brunswick, NJ) · Zbl 0679.90088 |
| [16] | Nemhauser, G., An Introduction to Probability Theory and Its Applications (1966), Wiley: Wiley New York · Zbl 0138.10207 |
| [17] | Papadimitriou, C. H.; Steiglitz, K., Combinatorial Optimization: Algorithms and Complexity (1982), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 0503.90060 |
| [18] | Paull, M. C., Algorithm Design: A Recursion Transformation Framework (1988), Wiley Interscience: Wiley Interscience New York |
| [19] | Reingold, E. M.; Nievergelt, J.; Deo, N., Combinatorial Algorithms: Theory and Practice (1977), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 0367.68032 |
| [20] | Ryder, B. G., Incremental data flow analysis, (Conference Record of the Tenth Annual ACM Symposium on the Principles of Programming Languages ACM SIGPLAN (1982)), 167-176 |
| [21] | Sierpinski, W., Elementary Theory of Numbers (1964), Hafner: Hafner New York · Zbl 0638.10001 |
| [22] | Tarjan, R. E., Fast algorithms for solving path problems, J. ACM, 28, 3, 594-614 (1981) · Zbl 0462.68042 |
| [23] | Tucker, A., Applied Combinatorics (1980), Wiley: Wiley New York · Zbl 0429.05001 |
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.
