Cormode, Graham and Veselý, Pavel (2020) Streaming algorithms for bin packing and vector scheduling. In: Bampis, Evripidis and Megow, Nicole, (eds.) Approximation and Online Algorithms : 17th International Workshop, WAOA 2019, Munich, Germany, September 12–13, 2019, Revised Selected Papers. Lecture Notes in Computer Science (11926). Cham : Springer International Publishing. ISBN 9783030394783
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
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.
| Item Type: | Book Item |
|---|---|
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science |
| Series Name: | Lecture Notes in Computer Science |
| Publisher: | Springer International Publishing |
| Place of Publication: | Cham |
| ISBN: | 9783030394783 |
| Book Title: | Approximation and Online Algorithms : 17th International Workshop, WAOA 2019, Munich, Germany, September 12–13, 2019, Revised Selected Papers |
| Editor: | Bampis, Evripidis and Megow, Nicole |
| Official Date: | 23 September 2020 |
| Dates: | Date Event 23 September 2020 Published UNSPECIFIED Accepted |
| Number: | 11926 |
| DOI: | 10.1007/978-3-030-39479-0_6 |
| Status: | Peer Reviewed |
| Publication Status: | Published |
| Related URLs: | |
| Persistent URL: | https://wrap.warwick.ac.uk/142356/ |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |