text: Numerous combinatorial optimization problems (knapsack, maximum-weight matching, etc.) can be expressed as : One is given a ground set @math , a collection @math of subsets thereof such that @math , and an objective (profit) function @math . The task is to choose a set @math that maximizes @math . We consider the version (, , both ICALP 2014) of such problems: The profit function @math (and possibly the set of feasible solutions @math ) 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 trade-off between good per-time 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 @math and the Hamming distance between the two characteristic vectors. We study multistage subset maximization problems in the setting, that is, @math (along with possibly @math ) 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 constant-competitive 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.
  @cite_0: We provide a framework for designing competitive online algorithms using regularization, a widely used technique in online learning, particularly in online convex optimization. An online algorithm that uses regularization serves requests by computing a solution, in each step, to an objective function involving a smooth convex regularization function. Applying the technique of regularization allows us to obtain new results in the domain of competitive analysis. We remark that competitive analysis and online learning are two widely studied frameworks for online decision-making settings. We show that even though there are significant differences in assumptions, goals, and techniques between the two fields, one can still benefit by introducing techniques from one field to the other. In our new framework we exhibit a general O(log m)-competitive deterministic algorithm for generating a fractional solution that satisfies a time-varying set of online covering and precedence constraints, where m is the number of variables. This framework allows to incorporate both service costs (over time) and setup costs into a host of applications. We then provide an O(log m log n)-competitive randomized algorithm for the online set cover problem with service cost, where m is the number of sets and n is the number of elements. This model allows for sets to be both added and deleted over time from a solution.
  @cite_4: Online learning and competitive analysis are two widely studied frameworks for online decision-making settings. Despite the frequent similarity of the problems they study, there are significant differences in their assumptions, goals, and techniques, hindering a unified analysis and richer interplay between the two. In this paper, we provide several contributions in this direction. We provide a single unified algorithm, which, by parameter tuning, interpolates between optimal regret for learning from experts (in online learning) and optimal competitive ratio for the metrical task systems problem (MTS) (in competitive analysis), improving upon previous results. The algorithm also allows us to obtain new regret bounds against “drifting” experts, which might be of independent interest. Moreover, our approach allows us to go beyond experts MTS, obtaining similar unifying results for structured action sets and “combinatorial experts,” whenever the setting has a certain matroid structure.
summary: @cite_4 and Buchbinder, Chen and Naor @cite_0 considered a multistage model and they studied the relation between the online learning and competitive analysis frameworks, mostly for fractional optimization problems.