𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A hard knapsack problem

✍ Scribed by Chia-Shin Chung; Ming S. Hung; Walter O. Rom

Publisher
John Wiley and Sons
Year
1988
Tongue
English
Weight
661 KB
Volume
35
Category
Article
ISSN
0894-069X

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

A stochastic linear knapsack problem
A stochastic linear knapsack problem
✍ Shōgo Shiode; Hiroaki Ishi; Toshio Nishida πŸ“‚ Article πŸ“… 1987 πŸ› John Wiley and Sons 🌐 English βš– 297 KB
Factoring Polynomials and the Knapsack P
Factoring Polynomials and the Knapsack Problem
✍ Mark van Hoeij πŸ“‚ Article πŸ“… 2002 πŸ› Elsevier Science 🌐 English βš– 222 KB

For several decades the standard algorithm for factoring polynomials f with rational coefficients has been the Berlekamp-Zassenhaus algorithm. The complexity of this algorithm depends exponentially on n, where n is the number of modular factors of f . This exponential time complexity is due to a com

Note: On the set-union knapsack problem
Note: On the set-union knapsack problem
✍ Olivier Goldschmidt; David Nehme; Gang Yu πŸ“‚ Article πŸ“… 1994 πŸ› John Wiley and Sons 🌐 English βš– 558 KB
Solving the generalized knapsack problem
Solving the generalized knapsack problem with variable coefficients
✍ Kaj Holmberg; Kurt JΓΆrnsten πŸ“‚ Article πŸ“… 1996 πŸ› John Wiley and Sons 🌐 English βš– 1012 KB

In this article we present methods based on Lagrangian duality and decomposition techniques for the generalized knapsack problem with variable coefficients. The Lagrangian dual is solved with subgradient optimization or interval bisection. We also describe a heuristic that yields primal feasible sol