Fully-Dynamic Bin Packing with Limited Repacking
share
We consider the bin packing problem in a fully-dynamic setting, where new items can arrive and old items may depart. The objective here is to obtain algorithms achieving low asymptotic competitive ratio while changing the packing sparingly between updates. We associate with each item i a movement cost c_i≥ 0. We wish to achieve good approximation guarantees while incurring a movement cost of β· c_i, either in the worst case, or in an amortized sense, for β as small as possible. We refer to this β as the recourse of the algorithm. We obtain tight or near-tight results for this problem for the following settings: (1) For general movement costs (the c_is are unconstrained), we show that with constant recourse one can almost match the best asymptotic competitive ratio of online bin packing, and show a complementary lower bound: fully-dynamic bin packing with small recourse is at least as hard as its online counterpart. (2) For unit movement costs (c_i=1 for all i), we use an LP-based approach to show a sharp threshold of α≈ 1.3871. Specifically, we show that for any ϵ>0, any algorithm with asymptotic competitive ratio α-ϵ must suffer either polynomially large additive terms or recourse. On the positive side, for any ϵ>0, we give an algorithm with asymptotic competitive ratio of α+ϵ, with an O(ϵ^-2) additive term and recourse O(ϵ^-2). (3) For volume movement costs (c_i=s_i for all i), we show a tight tradeoff between competitive ratio and amortized recourse. Hence, for amortized recourse, our work gives nearly-matching upper and lower bounds for all these three natural settings. Our last two results add to the small list of problems for which tight or nearly-tight tradeoffs between amortized recourse and asymptotic competitive ratio are known.
READ FULL TEXT