Problems involving the efficient arrangement of simple objects, as captured by bin packing and makespan scheduling, are fundamental tasks in combinatorial optimization. These are well understood in the traditional online and offline cases, but have been less well-studied when the volume of the input is truly massive, and cannot even be read into memory. This is captured by the streaming model of computation, where the aim is to approximate the cost of the solution in one pass over the data, using small space. As a result, streaming algorithms produce concise input summaries that approximately preserve the optimum value. We design the first efficient streaming algorithms for these fundamental problems in combinatorial optimization. For Bin Packing, we provide a streaming asymptotic @math -approximation with @math memory, where @math hides logarithmic factors. Moreover, such a space bound is essentially optimal. Our algorithm implies a streaming @math -approximation for Vector Bin Packing in @math dimensions, running in space @math . For the related Vector Scheduling problem, we show how to construct an input summary in space @math that preserves the optimum value up to a factor of @math , where @math is the number of identical machines.
For the scalar problem, the optimal competitive ratio is known to lie in the interval @math @cite_26 @cite_3 @cite_15 @cite_36 , which is substantially worse than what can be done by a simple streaming @math -approximation in space @math . Interestingly, for , the algorithm by Im al @cite_11 with ratio @math actually works in the online setting as well and needs space @math only during its execution (if the solution itself is not stored), which makes it possible to implement it in the streaming setting. This online ratio cannot be improved as there is a lower bound of @math @cite_11 @cite_16 , whereas in the streaming setting we can achieve a @math -approximation with a reasonable memory (or even @math for a fixed @math ). If all jobs have sufficiently small size, we improve the analysis in @cite_11 and show that the online algorithm achieves @math -approximation; see .
@cite_26 @cite_36 @cite_3 @cite_15 @cite_16 @cite_11
2095518199 2015871191 2001538186 2044781641 2779148821 2908654738
We study a classical problem in online scheduling. A sequence of jobs must be scheduled on m identical parallel machines. As each job arrives, its processing time is known. The goal is to minimize the makespan. [ J. Comput. System Sci., 51 (1995), pp. 359--366] gave a deterministic online algorithm that is 1.986-competitive. Karger, Phillips, and Torng [ J. Algorithms, 20 (1996), pp. 400--430] generalized the algorithm and proved an upper bound of 1.945. The best lower bound currently known on the competitive ratio that can be achieved by deterministic online algorithms is equal to 1.837. In this paper we present an improved deterministic online scheduling algorithm that is 1.923-competitive; for all @math . The algorithm is based on a new scheduling strategy, i.e., it is not a generalization of the approach by Also, the algorithm has a simple structure. Furthermore, we develop a better lower bound. We prove that, for general m, no deterministic online scheduling algorithm can be better than 1.852-competitive. We present a new on-line algorithm, MR, for non-preemptive scheduling of jobs with known processing times on m identical machines which beats the best previous algorithm for m⩾64. For m∞ its competitive ratio approaches 1+ (1+1 n 2) 2 <1.9201. Copyright 2000 © John Wiley & Sons, Ltd. We study randomized algorithms for the online vector bin packing and vector scheduling problems. For vector bin packing, we achieve a competitive ratio of O(d1 B), where d is the number of dimensions and B the size of a bin. This improves the previous bound of O(d1 (B−1)) by a polynomial factor, and is tight up to logarithmic factors. For vector scheduling, we show a lower bound of [EQUATION] on the competitive ratio of randomized algorithms, which is the first result for randomized algorithms and is asymptotically tight. Finally, we analyze the widely used "power of two choices' algorithm for vector scheduling, and show that its competitive ratio is [EQUATION], which is optimal up to the additive O(log log n) term that also appears in the scalar version of this algorithm. Modern data centers face a key challenge of effectively serving user requests that arrive online. Such requests are inherently multidimensional and characterized by demand vectors over multiple res...