Load optimization in a planar network

DOI10.1214/09-AAP676MaRDI QIDQ614115zbMATHFDO

Authors Charles Bordenave, Giovanni Luca Torrisi

Publication date 27 December 2010

Published in The Annals of Applied Probability (Search for Journal in Brave)

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

zbMATH Keywords

central limit theoremlarge deviationscalculus of variationslaw of large numberswireless networksEuclidean optimization

Mathematics Subject Classification ID

Large deviations (60F10) Central limit and other weak theorems (60F05) Combinatorial optimization (90C27) Communication networks in operations research (90B18)

Abstract: We analyze the asymptotic properties of a Euclidean optimization problem on the plane. Specifically, we consider a network with three bins and $n$ objects spatially uniformly distributed, each object being allocated to a bin at a cost depending on its position. Two allocations are considered: the allocation minimizing the bin loads and the allocation allocating each object to its less costly bin. We analyze the asymptotic properties of these allocations as the number of objects grows to infinity. Using the symmetries of the problem, we derive a law of large numbers, a central limit theorem and a large deviation principle for both loads with explicit expressions. In particular, we prove that the two allocations satisfy the same law of large numbers, but they do not have the same asymptotic fluctuations and rate functions.

Recommendations

• Functional strong law of large numbers for loads in a planar network model
• Performance of global load balancing by local adjustment
• Analysis of Simple Algorithms for Dynamic Load Balancing
• Perfectly balanced allocation
• How asymmetry helps load balancing

Cites work

• scientific article; zbMATH DE number 46153 (Why is no real title available?)
• scientific article; zbMATH DE number 1201586 (Why is no real title available?)
• scientific article; zbMATH DE number 1158743 (Why is no real title available?)
• scientific article; zbMATH DE number 3274494 (Why is no real title available?)
• A large deviations heuristic made precise
• Asymptotic analysis. Reprint
• Fundamentals of Wireless Communication
• Spatial Capacity of Multiple-Access Wireless Networks
• Uniform Central Limit Theorems

Cited in

(2)

• A problem in the optimal design of networks under transverse loading
• An efficient solution for mitigating light-load penalty in EPONs

This page was built for publication: Load optimization in a planar network

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