Chains-into-Bins Processes

DOI10.1007/978-3-642-19222-7_32zbMATH Open1326.68206arXiv1005.2616OpenAlexW3121504878MaRDI QIDQ3000519FDOQ3000519

Authors: Tuğkan Batu, Petra Berenbrink, Colin Cooper 

Publication date: 19 May 2011

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Abstract: The study of {em balls-into-bins processes} or {em occupancy problems} has a long history. These processes can be used to translate realistic problems into mathematical ones in a natural way. In general, the goal of a balls-into-bins process is to allocate a set of independent objects (tasks, jobs, balls) to a set of resources (servers, bins, urns) and, thereby, to minimize the maximum load. In this paper, we analyze the maximum load for the {em chains-into-bins} problem, which is defined as follows. There are $n$ bins, and $m$ objects to be allocated. Each object consists of balls connected into a chain of length $ell$, so that there are $mell$ balls in total. We assume the chains cannot be broken, and that the balls in one chain have to be allocated to $ell$ consecutive bins. We allow each chain $d$ independent and uniformly random bin choices for its starting position. The chain is allocated using the rule that the maximum load of any bin receiving a ball of that chain is minimized. We show that, for $dge2$ and $mcdotell=O(n)$, the maximum load is $((lnlnm)/lnd)+O(1)$ with probability $1-ildeO(1/m^{d-1})$.

Full work available at URL: https://arxiv.org/abs/1005.2616

Recommendations

• Chains-into-bins processes
• Batched bin packing
• Chained flows
• Mapping a chain task to chained processors
• More on batched bin packing
• Bin decompositions
• Granular chains
• Packing batches of items into a single bin
• Bicategories of processes

zbMATH Keywords

random processesballs-into-bins processeschains-into-bins processesoffline assignment

Mathematics Subject Classification ID

Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Combinatorics in computer science (68R05)

Cites Work

• How asymmetry helps load balancing
• Title not available (Why is that?)
• Balanced Allocations
• Balanced allocation on graphs
• Title not available (Why is that?)
• Tail Bounds and Expectations for Random Arc Allocation and Applications
• Balanced Allocations: The Heavily Loaded Case

Cited In (1)

• Chains-into-bins processes

This page was built for publication: Chains-into-Bins Processes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3000519)