An AFPTAS for variable sized bin packing with general activation costs

By: Epstein L., Levin A.
Published in: Journal of Computer and System Sciences
SDGs : SDG 07  |  Units: Natural Sciences  | Time: 2017 |  Link
Description: Motivated by issues of minimizing energy consumption, we study variable sized bin packing with general costs. In this pr oblem we are given an unlimited supply of bins of different types. A bin of each type has a size and a cost. A set of items is given, where each item has a size in (0,1]. The goal is to assign the items to bins, so that the total cost is minimized. It is allowed to use multiple instances of any of the bin types, but this counts towards the total cost. The problem is general as the cost of a bin has no relation to its size. We design an AFPTAS for the problem by introducing new reduction methods and separation techniques, thus providing new insights into this interesting optimization problem. Furthermore, we use this AFPTAS to provide an AFPTAS for the bin packing with bin utilization cost problem. © 2016 Elsevier Inc.