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

On PreemptiveResource Constrained Scheduling: Polynomial-Time Approximation Schemes

โœ Scribed by Jansen, Klaus; Porkolab, Lorant

Book ID
118198066
Publisher
Society for Industrial and Applied Mathematics
Year
2006
Tongue
English
Weight
231 KB
Volume
20
Category
Article
ISSN
0895-4801

No coin nor oath required. For personal study only.

๐Ÿ“œ SIMILAR VOLUMES

Polynomial time approximation schemes fo
Polynomial time approximation schemes for class-constrained packing problems
โœ Hadas Shachnai; Tami Tamir ๐Ÿ“‚ Article ๐Ÿ“… 2001 ๐Ÿ› Springer US ๐ŸŒ English โš– 207 KB

We consider variants of the classic bin packing and multiple knapsack problems, in which sets of items of di erent classes (colours) need to be placed in bins; the items may have di erent sizes and values. Each bin has a limited capacity, and a bound on the number of distinct classes of items it can

On the efficiency of polynomial time app
On the efficiency of polynomial time approximation schemes
โœ Marco Cesati; Luca Trevisan ๐Ÿ“‚ Article ๐Ÿ“… 1997 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 630 KB

A polynomial time approximation scheme (PTAS) for an optimization problem A is an algorithm that given in input an instance of A and E > 0 find;,; (1 + E)-approximate solution in time that is polynomial for each fixed E. Typical running times are no(+) or 2"' n. While algorithms of the former kind t