Cormode, Graham and Veselý, Pavel (2021) Streaming algorithms for bin packing and vector scheduling. Theory of Computing Systems, 65 . pp. 916-942. doi:10.1007/s00224-020-10011-y ISSN 1432-4350.
Preview |
PDF
WRAP-streaming-algorithms-bin-packing-vector-scheduling-Cormode-2020.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution 4.0. Download (588kB) | Preview |
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
| Item Type: | Journal Article |
|---|---|
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software |
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science |
| Library of Congress Subject Headings (LCSH): | Computer algorithms, Approximation algorithms , Online algorithms , Combinatorial optimization |
| Journal or Publication Title: | Theory of Computing Systems |
| Publisher: | Springer New York LLC |
| ISSN: | 1432-4350 |
| Official Date: | August 2021 |
| Dates: | Date Event August 2021 Published 12 November 2020 Available 27 September 2020 Accepted |
| Volume: | 65 |
| Page Range: | pp. 916-942 |
| DOI: | 10.1007/s00224-020-10011-y |
| Status: | Peer Reviewed |
| Publication Status: | Published |
| Access rights to Published version: | Open Access (Creative Commons open licence) |
| Date of first compliant deposit: | 17 November 2020 |
| Date of first compliant Open Access: | 18 November 2020 |
| RIOXX Funder/Project Grant: | Project/Grant ID RIOXX Funder Name Funder ID |
| URI: | https://wrap.warwick.ac.uk/144580/ |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |