Chains-into-Bins Processes

DOI10.1007/978-3-642-19222-7_32MaRDI QIDQ3000519zbMATH OpenOpenAlexFDO

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)

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

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)

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})$.

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

Cites work

• scientific article; zbMATH DE number 5485459 (Why is no real title available?)
• scientific article; zbMATH DE number 1857645 (Why is no real title available?)
• Balanced Allocations
• Balanced Allocations: The Heavily Loaded Case
• Balanced allocation on graphs
• How asymmetry helps load balancing
• Tail Bounds and Expectations for Random Arc Allocation and Applications

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)