We study online multidimensional variants of the generalized assignment problem which are used to model prominent real-world applications, such as the assignment of virtual machines with multiple resource requirements to physical infrastructure in cloud computing. These problems can be seen as an extension of the well known secretary problem and thus the standard online worst-case model cannot provide any performance guarantee. The prevailing model in this case is the random-order model, which provides a useful realistic and robust alternative. Using this model, we study the @math -dimensional generalized assignment problem, where we introduce a novel technique that achieves an @math -competitive algorithms and prove a matching lower bound of @math . Furthermore, our algorithm improves upon the best-known competitive-ratio for the online (one-dimensional) generalized assignment problem and the online knapsack problem.
The online knapsack problem, which generalizes the multiple-secretary problem, was studied by @cite_2 who presented an @math -competitive algorithm. It was later improved by the work of @cite_11 on online GAP, which generalizes all of the above problems. They presented an @math -competitive algorithm which is the best-known competitive-ratio for online GAP and the online knapsack problem. Our result for VGAP improves on that.
@cite_11 @cite_2
2899383020 2164792208
We study packing linear programs (LPs) in an online model where the columns are presented to the algorithm in random order. This natural problem was investigated in various recent studies motivated, e.g., by online ad allocations and yield management, where rows correspond to resources and columns to requests specifying demands for resources. Our main contribution is a @math -competitive online algorithm. Here @math denotes the column sparsity, i.e., the maximum number of resources that occur in a single column, and @math denotes the capacity ratio @math , i.e., the ratio between the capacity of a resource and the maximum demand for this resource. In other words, we achieve a @math -approximation if the capacity ratio satisfies @math , which is known to be the best possible for any (randomized) online algorithms. Our result improves exponentially on previous work with respect to the capacity ratio. In contrast to existing results on packing LP ... We consider situations in which a decision-maker with a fixed budget faces a sequence of options, each with a cost and a value, and must select a subset of them online so as to maximize the total value. Such situations arise in many contexts, e.g., hiring workers, scheduling jobs, and bidding in sponsored search auctions. This problem, often called the online knapsack problem, is known to be inapproximable. Therefore, we make the enabling assumption that elements arrive in a randomorder. Hence our problem can be thought of as a weighted version of the classical secretary problem, which we call the knapsack secretary problem. Using the random-order assumption, we design a constant-competitive algorithm for arbitrary weights and values, as well as a e-competitive algorithm for the special case when all weights are equal (i.e., the multiple-choice secretary problem). In contrast to previous work on online knapsack problems, we do not assume any knowledge regarding the distribution of weights and values beyond the fact that the order is random.