The Library
Streaming algorithms for bin packing and vector scheduling
Tools
Tools
Tools
Cormode, Graham and Veselý, Pavel (2019) Streaming algorithms for bin packing and vector scheduling. In: Workshop on Approximation and Online Algorithms, Munich, Germany, 9-13 Sep 2019. Published in: Approximation and Online Algorithms. WAOA 2019, 11926 pp. 72-88. ISBN 9783030394783. doi:10.1007/978-3-030-39479-0_6
|
PDF
WRAP-streaming-algorithms-bin-packing-vector-Cormode-2019.pdf - Accepted Version - Requires a PDF viewer. Download (749Kb) | Preview |
Official URL: https://doi.org/10.1007/978-3-030-39479-0_6
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 with O˜(1ε) memory, where O˜ hides logarithmic factors. Moreover, such a space bound is essentially optimal. Our algorithm implies a streaming d+ε -approximation for Vector Bin Packing in d dimensions, running in space O˜(dε) . For the related Vector Scheduling problem, we show how to construct an input summary in space O˜(d2⋅m/ε2) that preserves the optimum value up to a factor of 2−1m+ε , where m is the number of identical machines.
| Item Type: | Conference Item (Paper) | ||||||
|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||||
| Divisions: | Faculty of Science > Computer Science | ||||||
| Library of Congress Subject Headings (LCSH): | Online algorithms , Combinatorial packing and covering -- Data processing, Computer algorithms, Combinatorial optimization | ||||||
| Series Name: | Lecture Notes in Computer Science | ||||||
| Journal or Publication Title: | Approximation and Online Algorithms. WAOA 2019 | ||||||
| Publisher: | Springer | ||||||
| ISBN: | 9783030394783 | ||||||
| Official Date: | 20 July 2019 | ||||||
| Dates: |
|
||||||
| Volume: | 11926 | ||||||
| Page Range: | pp. 72-88 | ||||||
| DOI: | 10.1007/978-3-030-39479-0_6 | ||||||
| Status: | Peer Reviewed | ||||||
| Publication Status: | Published | ||||||
| Access rights to Published version: | Restricted or Subscription Access | ||||||
| RIOXX Funder/Project Grant: |
|
||||||
| Conference Paper Type: | Paper | ||||||
| Title of Event: | Workshop on Approximation and Online Algorithms | ||||||
| Type of Event: | Workshop | ||||||
| Location of Event: | Munich, Germany | ||||||
| Date(s) of Event: | 9-13 Sep 2019 | ||||||
| Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
