×

A min-cost bin covering problem and its algorithm. (Chinese. English summary) Zbl 1174.68789

Summary: A new variant of the min-cost Bin Covering Problem (min-cost BCP) is proposed, in which each item has two parameters, capacity and cost. For the offline min-cost BCP, we present an algorithm C-FF\(_1\). It is proved that the C-FF\(_1\) algorithm has an asymptotic worst-case performance ratio of 1/2. For the online min-cost BCP, we also present an online algorithm C-FF\(_2\) with an absolute worst-case ratio 1/2. Moreover, we provide lower worst-case bounds of any online and offline algorithms.

MSC:

68W25 Approximation algorithms
68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
05B40 Combinatorial aspects of packing and covering