๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Approximate algorithms for some generalized knapsack problems

โœ Scribed by Ashok K. Chandra; D.S. Hirschberg; C.K. Wong

Publisher
Elsevier Science
Year
1976
Tongue
English
Weight
361 KB
Volume
3
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

๐Ÿ“œ SIMILAR VOLUMES

Combinatorial Approximation Algorithms f
Combinatorial Approximation Algorithms for Generalized Flow Problems
โœ Jeffrey D Oldham ๐Ÿ“‚ Article ๐Ÿ“… 2001 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 226 KB

Generalized network flow problems generalize normal network flow problems by specifying a flow multiplier ยต v w for each arc v w . For every unit of flow entering the arc, ยต v w units of flow exit. We present a strongly polynomial algorithm for a single-source generalized shortest paths problem, usi

Fast and Scalable Parallel Algorithms fo
Fast and Scalable Parallel Algorithms for Knapsack-like Problems
โœ Afonso Ferreira; John Michael Robson ๐Ÿ“‚ Article ๐Ÿ“… 1996 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 403 KB

We present two new algorithms for searching in sorted X ุ‰ Y ุ‰ R ุ‰ S, one based on heaps and the other on sampling. Each of the algorithms runs in time O(n 2 log n) (n being the size of the sorted arrays X, Y, R, and S). Hence in each case, by constructing arrays of size n โ€ซุโ€ฌ O(2 s/4 ), we obtain a