Andrew Chi-Chih Yao
- 1 Aho, A V, HOr'CROVT, J E, AND ULLMAN, J D The Design and Analysts of Computer Algorithms AddLson-Wesley, Reading, Mass, 1974 Google Scholar
- 2 BoaoolN, A On relating time and space to size and depth SIAM J Comput. 6 (1977), 733-744.Google Scholar
- 3 DOBK1N, D, ,NO LIPTON, R J A lower bound of n2/2 on hnear search programs for the knapsack problem d Comgut Syst Sct 16(1978), 413-417Google Scholar
- 4 DYMOND, PW, AND COOK, S A Hardware complexity and parallel computation Proc 21st Ann IEEE Syrup on Foundations of Computer Science, Syracuse, N Y, Oct 1980, pp. 360-372.Google Scholar
- 5 HONG JAI-.WEI On slmdanty and duality of computatmn Proc 21st Ann. IEEE Symp on Foundatmns of Computer Science, Syracuse, N Y, Oct 1980, 348-359Google Scholar
- 6 LAWLER, E L Combtnatortal Opttmtzalton Networks and Matrolds Holt, Rinehart and Winston, New York, 1976Google Scholar
- 7 MILNOR, J On the Bern numbers of real vartettes Am Math Soe 15 (1964), 275-280.Google Scholar
- 8 STEELE, J.M, AND YAO, A.C.Lower bounds for algebraic decaston trees. J. Algorithms 3 (1982), l--8.Google Scholar
Index Terms
- On Parallel Computation for the Knapsack Problem
Recommendations
Solving the Temporal Knapsack Problem via Recursive Dantzig-Wolfe Reformulation
The Temporal Knapsack Problem (TKP) is a generalization of the standard Knapsack Problem where a time horizon is considered, and each item consumes the knapsack capacity during a limited time interval only. In this paper we solve the TKP using what we ...
Exact Solution of the Quadratic Knapsack Problem
<P>The Quadratic Knapsack Problem (QKP) calls for maximizing a quadratic objective function subject to a knapsack constraint, where all coefficients are assumed to be nonnegative and all variables are binary. The problem has applications in location and ...
Exact approaches for the knapsack problem with setups
We study a generalization of the knapsack problem in which items are partitioned into classes, known as knapsack problem with setups (KPS).We study three alternative Integer Linear Programming formulations for KPS.We design efficient algorithms to ...
Comments