Seminário de Teoria da Computação

 Approximation Schemes for a Class Constrained Knapsack Problem


                       Eduardo C. Xavier
               Sexta-feira, 18 de outubro de 2002
                       Sala 96  13:00hs

We study a generalized version of the knapsack problem and present
approximation algorithms for some versions of it. Given an integer K,
a set of items S, each item i with value v_i, size s_i and a class
c_i, find a subset of S of maximum total value such that items are
grouped in compartments. Each compartment must have only items of one
class and must be separated by the subsequent compartment by a wall of
size d. Moreover, two subsequent walls must stay a distance of at
least d_min and at most d_max. The total size used for the
compartments and the walls must be at most K. This problem have
practical applications on cutting-stock problems