Class Constrained Bin Covering |
| |
Authors: | Leah Epstein Csanád Imreh Asaf Levin |
| |
Affiliation: | 1. Department of Mathematics, University of Haifa, 31905, Haifa, Israel 2. Department of Informatics, University of Szeged, 6720, Szeged, Hungary 3. Department of Statistics, The Hebrew University, 91905, Jerusalem, Israel
|
| |
Abstract: | We study the following variant of the bin covering problem. We are given a set of unit sized items, where each item has a
color associated with it. We are given an integer parameter k≥1 and an integer bin size B≥k. The goal is to assign the items (or a subset of the items) into a maximum number of subsets of at least B items each, such that in each such subset the total number of distinct colors of items is at least
k. We study both the offline and the online variants of this problem. We first design an optimal polynomial time algorithm
for the offline problem. For the online problem we give a lower bound of 1+H
k−1 (where H
k−1 denotes the (k−1)-th harmonic number), and an O(k)-competitive algorithm. Finally, we analyze the performance of the natural heuristic First fit. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|