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.
The Multistage Max-Min Fair Allocation problem has been studied in the offline and the online settings in @cite_12 . This problem corresponds to a multistage variant of the Santa Klaus problem. For the off-line setting, the authors showed that the multistage version of the problem is much harder than the static one. They provided constant factor approximation algorithms for the off-line setting. For the online setting they proposed a constant competitive ratio for SSFS-type evolving instances and they proved that it is not possible to find an online algorithm with bounded competitive ratio for GE-type evolving instances. Finally, they showed that in the 1-lookahead case, where at time step @math we know the instance of time step @math , it is possible to get a constant approximation ratio.
@cite_12
2808191361
We consider the over-time version of the Max-Min Fair Allocation problem. Given a time horizon @math , with at each time t a set of demands and a set of available resources that may change over the time defining instance @math , we seek a sequence of solutions @math that (1) are near-optimal at each time t , and (2) as stable as possible (inducing small modification costs). We focus on the impact of the knowledge of the future on the quality and the stability of the returned solutions by distinguishing three settings: the off-line setting where the whole set of instances through the time horizon is known in advance, the on-line setting where no future instance is known, and the k -lookahead setting where at time t , the instances at times @math are known. We first consider the case without restrictions where the set of resources and the set of agents are the same for all instances and where every resource can be allocated to any agent. For the off-line setting, we show that the over-time version of the problem is much harder than the static one, since it becomes @math -hard even for families of instances for which the static problem is trivial. Then, we provide a @math -approximation algorithm for the off-line setting using as subroutine a ρ-approximation algorithm for the static version. We also give a @math -competitive algorithm for the online setting using also as subroutine a ρ-approximation algorithm for the static version. Furthermore, for the case with restrictions, we show that in the off-line setting it is possible to get a polynomial-time algorithm with the same approximation ratio as in the case without restrictions. For the online setting, we prove that it is not possible to find an online algorithm with bounded competitive ratio. For the 1-lookahead setting however, we give a @math -approximation algorithm using as subroutine a ρ-approximation algorithm for the static version. This paper investigates the problem of scheduling jobs on multiple speed-scaled processors without migration, i.e., we have constant α > 1 such that running a processor at speed s results in energy consumption s#945; per time unit. We consider the general case where each job has a monotonously increasing cost function that penalizes delay. This includes the so far considered cases of deadlines and flow time. For any type of delay cost functions, we obtain the following results: Any β-approximation algorithm for a single processor yields a randomized βBα-approximation algorithm for multiple processors, where Bα is the αth Bell number, that is, the number of partitions of a set of size α. Analogously, we show that any β-competitive online algorithm for a single processor yields a βBα-competitive online algorithm for multiple processors. Finally, we show that any β-approximation algorithm for multiple processors with migration yields a deterministic βBα-approximation algorithm for multiple processors without migration. These facts improve several approximation ratios and lead to new results. For instance, we obtain the first constant factor online and offline approximation algorithm for multiple processors without migration for arbitrary release times, deadlines, and job sizes. All algorithms are based on the surprising fact that we can remove migration with a blowup of Bα in expectation. We consider a significant generalization of the Adwords problem by allowing arbitrary concave returns, and we characterize the optimal competitive ratio achievable. The problem considers a sequence of items arriving online that have to be allocated to agents, with different agents bidding different amounts. The objective function is the sum, over each agent i, of a monotonically non-decreasing concave function Mi : R+ -> R+ of the total amount allocated to i. All variants of online matching problems (including the Adwords problem) studied in the literature consider the special case of budgeted linear functions, that is, functions of the form Mi(ui) = min ui,Bi for some constant Bi. The distinguishing feature of this paper is in allowing arbitrary concave returns. The main result of this paper is that for each concave function M, there exists a constant F(M) ≤ 1 such that: there exists an algorithm with competitive ratio of miniF(Mi), independent of the sequence of items. No algorithm has a competitive ratio larger than F(M) over all instances with Mi= M for all i. Our algorithm is based on the primal-dual paradigm and makes use of convex programming duality. The upper bounds are obtained by formulating the task of finding the right counterexample as an optimization problem. This path takes us through the calculus of variations which deals with optimizing over continuous functions. The algorithm and the upper bound are related to each other via a set of differential equations, which points to a certain kind of duality between them. We study the online stochastic bipartite matching problem, in a form motivated by display ad allocation on the Internet. In the online, but adversarial case, the celebrated result of Karp, Vazirani and Vazirani gives an approximation ratio of @math , a very familiar bound that holds for many online problems; further, the bound is tight in this case. In the online, stochastic case when nodes are drawn repeatedly from a known distribution, the greedy algorithm matches this approximation ratio, but still, no algorithm is known that beats the @math bound.Our main result is a @math -approximation online algorithm for stochastic bipartite matching, breaking this @math barrier. Furthermore, we show that no online algorithm can produce a @math approximation for an arbitrarily small @math for this problem. Our algorithms are based on computing an optimal offline solution to the expected instance, and using this solution as a guideline in the process of online allocation. We employ a novel application of the idea of the power of two choices from load balancing: we compute two disjoint solutions to the expected instance, and use both of them in the online algorithm in a prescribed preference order. To identify these two disjoint solutions, we solve a max flow problem in a boosted flow graph, and then carefully decompose this maximum flow to two edge-disjoint (near-) matchings. In addition to guiding the online decision making, these two offline solutions are used to characterize an upper bound for the optimum in any scenario. This is done by identifying a cut whose value we can bound under the arrival distribution. At the end, we discuss extensions of our results to more general bipartite allocations that are important in a display ad application.