Streaming Algorithms for Bin Packing and Vector Scheduling

Journal article

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 wit

Authors: Cormode, G; Veselý, P

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Springer
• Journal: Theory of Computing Systems
• Volume: 65
• Issue: 6
• Pages: 916-942
• Publication date: 2020-11-12
• DOI: 10.1007/s00224-020-10011-y
• EISSN: 1433-0490
• ISSN: 1432-4350
• Language: English
• Keywords: Algorithm; Computer science; Machine learning; Bin; Artificial intelligence