Online Bin Covering with Limited Migration Semionline models where decisions may be revoked in a limited way have been studied extensively in the last years.  :19,is motivated by the fact that the pure online model :19,is often too restrictive to model realworld applications, where some changes might be allowed. A wellstudied measure of the amount of decisions that can be revoked :19,is the migration factor beta: When an object o of size s(o) arrives, the decisions for objects of total size at most betacdot s(o) may be revoked. Usually beta should be a constant. This means that a small object only leads to small changes. This measure has been successfully investigated for different, classic problems such as bin packing or makespan minimization. The dual of makespan minimization  the Santa Claus or machine covering problem  has also been studied, whereas the dual of bin packing  the bin covering problem  has not been looked at from such a perspective.  :156,this work, we extensively study the bin covering problem with migration in different scenarios. We develop algorithms both for the static case  where only insertions are allowed  and for the dynamic case, where items may also depart. We also develop lower bounds for these scenarios both for amortized migration and for worstcase migration showing that our algorithms have nearly optimal migration factor and asymptotic competitive ratio (up to an arbitrary small eps). We therefore resolve the competitiveness of the bin covering problem with migration.

Online Multistage Subset Maximization Problems. Numerous combinatorial optimization problems (knapsack, maximumweight matching, etc.) can be expressed as emphsubset maximization problems: One is given a ground set N1,dots,n, a collection mathcalFsubseteq 2N of subsets thereof such that emptysetinmathcalF, and an objective (profit) function p:mathcalFrightarrowmathbbR_. The task is to choose a set SinmathcalF that maximizes p(S). We consider the emphmultistage version (Eisenstat et al., Gupta et al., both ICALP 2014) of such problems: The profit function p_t (and possibly the set of feasible solutions mathcalF_t) may change over time. Since in many applications changing the solution is costly, the task becomes to find a sequence of solutions that optimizes the tradeoff between good pertime solutions and stable solutions taking into account an additional similarity bonus. As similarity measure for two consecutive solutions, we consider either the size of the intersection of the two solutions or the difference of n and the Hamming distance between the two characteristic vectors. We study multistage subset maximization problems in the emphonline setting, that is, p_t (along with possibly mathcalF_t) only arrive one by one and, upon such an arrival, the online algorithm has to output the corresponding solution without knowledge of the future. We develop general techniques for online multistage subset maximization and thereby characterize those models (given by the type of data evolution and the type of similarity measure) that admit a constantcompetitive online algorithm. When no constant competitive ratio is possible, we employ lookahead to circumvent this issue. When a constant competitive ratio is possible, we provide almost matching lower and upper bounds on the best achievable one.