Streaming Algorithms for Bin Packing and Vector Scheduling
- PDF / 588,253 Bytes
- 27 Pages / 439.642 x 666.49 pts Page_size
- 33 Downloads / 178 Views
Streaming Algorithms for Bin Packing and Vector Scheduling Graham Cormode1 · Pavel Vesely´ 1 Accepted: 27 September 2020 © The Author(s) 2020
Abstract 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 (1 + ε)-approximation hides logarithmic factors. Moreover, such a space bound is 1 , where O with O ε essentially optimal. Our algorithm implies a streaming (d + ε)-approximation for d . For the related VECTOR BIN PACKING in d dimensions, running in space O ε VECTOR SCHEDULING problem, we show how to construct an input summary in 2 · m/ε2 ) that preserves the optimum value up to a factor of 2 − 1 + ε, space O(d m where m is the number of identical machines. Keywords Streaming algorithms · Bin packing · Scheduling
This article belongs to the Topical Collection: Special Issue on Approximation and Online Algorithms (2019) Guest Editors: Evripidis Bampis and Nicole Megow The work is supported by European Research Council grant ERC-2014-CoG 647557. A preliminary version of this work appears in [15] . Graham Cormode
[email protected] Pavel Vesel´y [email protected] 1
Department of Computer Science, University of Warwick, Coventry, UK
Theory of Computing Systems
1 Introduction The streaming model captures many scenarios when we must process very large volumes of data, which cannot fit into the working memory. The algorithm makes one or more passes over the data with a limited memory, but does not have random access to the data. Thus, it needs to extract a concise summary of the huge input, which can be used to approximately answer the problem under consideration. The main aim is to provide a good trade-off between the space used for processing the input stream (and hence, the summary size) and the accuracy of the (best possible) answer computed from the summary. Other relevant parameters are the time and space needed to make the estimate, and the number of passes, ideally equal to one. While there have been many effective streaming algorithms designed for a range of problems in statistics, optimization, and graph algorithms (see surveys by Muthukrishnan [39] and McGregor [38]), there has been little attention paid to the core problems of packing and scheduling. These are fundamental abstractions, which form the basis of many generalizations and extensions [13,
Data Loading...
