Graphical balanced allocations and the (1 + β)‐choice process. Issue 4 (22nd July 2014)

• Record Type: Journal Article
• Authors: Peres, Yuval; Talwar, Kunal; Wieder, Udi
• Is Part Of: Random structures & algorithms. Volume 47:Issue 4(2015)
• Page Start: 760
• Page End: 775
• Publication Date: 2014-07-22
• Subjects: Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20558
• Languages: English
• ISSNs: 1042-9832

Abstract

<abstract abstract-type="main"> <title>Abstract</title> <p>Suppose <italic>m</italic> balls are sequentially thrown into <italic>n</italic> bins where each ball goes into a random bin. It is well‐known that the gap between the load of the most loaded bin and the average is <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgkrnvgqzz" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20558:rsa20558-math-0001" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mo>Θ</mml:mo><mml:mo stretchy="false">(</mml:mo><mml:msqrt><mml:mrow><mml:mfrac><mml:mrow><mml:mi>m</mml:mi><mml:mi>log</mml:mi><mml:mi>n</mml:mi></mml:mrow><mml:mi>n</mml:mi></mml:mfrac></mml:mrow></mml:msqrt><mml:mo stretchy="false">)</mml:mo></mml:mrow></mml:math></alternatives></inline-formula>, for large <italic>m</italic>. If each ball goes to the lesser loaded of two random bins, this gap dramatically reduces to <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgkrnvgr3h" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20558:rsa20558-math-0002" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mo>Θ</mml:mo><mml:mo stretchy="false">(</mml:mo><mml:mi>log</mml:mi><mml:mi>log</mml:mi><mml:mi>n</mml:mi><mml:mo stretchy="false">)</mml:mo></mml:mrow></mml:math></alternatives></inline-formula> independent of <italic>m</italic>. Consider a constrained setting where not all pairs of bins can be sampled. We are given a graph where each node corresponds to a bin. The process sequentially samples an edge from the graph and places a ball in the lesser loaded of its endpoints. We show the gap is at most <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgkrnvgr20" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20558:rsa20558-math-0003" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>O</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mi>log</mml:mi><mml:mi>n</mml:mi><mml:mo>/</mml:mo><mml:mo>σ</mml:mo><mml:mo stretchy="false">)</mml:mo></mml:mrow></mml:math></alternatives></inline-formula> where <italic>σ</italic> is the edge expansion of the graph. Our results extend naturally to the hypergraph version of this question. Our technique involves a tight analysis of what we call the "<inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgkrnvgr1g" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20558:rsa20558-math-0004" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mo stretchy="false">(</mml:mo><mml:mn>1</mml:mn><mml:mo>+</mml:mo><mml:mo>β</mml:mo><mml:mo stretchy="false">)</mml:mo></mml:mrow></mml:math></alternatives></inline-formula>‐choice" process for some parameter <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgkrnvgr0z" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20558:rsa20558-math-0005" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mo>β</mml:mo><mml:mo>∈</mml:mo><mml:mo stretchy="false">(</mml:mo><mml:mn>0</mml:mn><mml:mo>, </mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="false">)</mml:mo></mml:mrow></mml:math></alternatives></inline-formula>: each ball goes to a random bin with probability <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgkrnvgqwx" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20558:rsa20558-math-0006" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mo stretchy="false">(</mml:mo><mml:mn>1</mml:mn><mml:mo>−</mml:mo><mml:mo>β</mml:mo><mml:mo stretchy="false">)</mml:mo></mml:mrow></mml:math></alternatives></inline-formula> and the lesser loaded of two random bins with probability <italic>β</italic>. For this process we show that the gap is <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgkrnvgqvd" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20558:rsa20558-math-0007" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mo>Θ</mml:mo><mml:mo stretchy="false">(</mml:mo><mml:mi>log</mml:mi><mml:mi>n</mml:mi><mml:mo>/</mml:mo><mml:mo>β</mml:mo><mml:mo stretchy="false">)</mml:mo></mml:mrow></mml:math></alternatives></inline-formula>, irrespective of <italic>m</italic>. Moreover the gap stays at <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgkrnvgqsc" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20558:rsa20558-math-0008" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mo>Θ</mml:mo><mml:mo stretchy="false">(</mml:mo><mml:mi>log</mml:mi><mml:mi>n</mml:mi><mml:mo>/</mml:mo><mml:mo>β</mml:mo><mml:mo stretchy="false">)</mml:mo></mml:mrow></mml:math></alternatives></inline-formula> in the weighted case for a large class of weight distributions. No non‐trivial bounds were previously known in the weighted case, even for the 2‐choice case. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 47, 760–775, 2015</p> </abstract>