A rounding technique to construct approximation algorithms for knapsack and partition-type problems - Kovalyov, Y. Mikhail (Zielona Góra: Uniwersytet Zielonogórski)
A technique to develop E-approximation schemes for mathematical programming problems is described based on the examples of knapsack and partition-type problems. The technique consists in the application of the dynamic programming algorithm to a relaxed problem constructed from the original one by rounding the values of the objective function and variables. The technique is applied to construct fully polynomial approximation schemes for some single and parallel machine scheduling problems with batch set-up times.
Keywords: sterowanie; sterowanie-teoria; sztuczna inteligencja; matematyka stosowana; informatyka