# The Total Acquisition Number Of The Randomly Weighted Path

Anant Godbole; Elizabeth Kelley; Emily Kurtz; Paweł Prałat; Yiguang Zhang

Discussiones Mathematicae Graph Theory (2017)

- Volume: 37, Issue: 4, page 919-934
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topAnant Godbole, et al. "The Total Acquisition Number Of The Randomly Weighted Path." Discussiones Mathematicae Graph Theory 37.4 (2017): 919-934. <http://eudml.org/doc/288291>.

@article{AnantGodbole2017,

abstract = {There exists a significant body of work on determining the acquisition number at(G) of various graphs when the vertices of those graphs are each initially assigned a unit weight. We determine properties of the acquisition number of the path, star, complete, complete bipartite, cycle, and wheel graphs for variations on this initial weighting scheme, with the majority of our work focusing on the expected acquisition number of randomly weighted graphs. In particular, we bound the expected acquisition number E(at(Pn)) of the n-path when n distinguishable “units” of integral weight, or chips, are randomly distributed across its vertices between 0.242n and 0.375n. With computer support, we improve it by showing that E(at(Pn)) lies between 0.29523n and 0.29576n. We then use subadditivity to show that the limiting ratio lim E(at(Pn))/n exists, and simulations reveal more exactly what the limiting value equals. The Hoeffding-Azuma inequality is used to prove that the acquisition number is tightly concentrated around its expected value. Additionally, in a different context, we offer a non-optimal acquisition protocol algorithm for the randomly weighted path and exactly compute the expected size of the resultant residual set.},

author = {Anant Godbole, Elizabeth Kelley, Emily Kurtz, Paweł Prałat, Yiguang Zhang},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {total acquisition number; Poissonization; dePoissonization; Maxwell-Boltzman and Bose-Einstein allocation.},

language = {eng},

number = {4},

pages = {919-934},

title = {The Total Acquisition Number Of The Randomly Weighted Path},

url = {http://eudml.org/doc/288291},

volume = {37},

year = {2017},

}

TY - JOUR

AU - Anant Godbole

AU - Elizabeth Kelley

AU - Emily Kurtz

AU - Paweł Prałat

AU - Yiguang Zhang

TI - The Total Acquisition Number Of The Randomly Weighted Path

JO - Discussiones Mathematicae Graph Theory

PY - 2017

VL - 37

IS - 4

SP - 919

EP - 934

AB - There exists a significant body of work on determining the acquisition number at(G) of various graphs when the vertices of those graphs are each initially assigned a unit weight. We determine properties of the acquisition number of the path, star, complete, complete bipartite, cycle, and wheel graphs for variations on this initial weighting scheme, with the majority of our work focusing on the expected acquisition number of randomly weighted graphs. In particular, we bound the expected acquisition number E(at(Pn)) of the n-path when n distinguishable “units” of integral weight, or chips, are randomly distributed across its vertices between 0.242n and 0.375n. With computer support, we improve it by showing that E(at(Pn)) lies between 0.29523n and 0.29576n. We then use subadditivity to show that the limiting ratio lim E(at(Pn))/n exists, and simulations reveal more exactly what the limiting value equals. The Hoeffding-Azuma inequality is used to prove that the acquisition number is tightly concentrated around its expected value. Additionally, in a different context, we offer a non-optimal acquisition protocol algorithm for the randomly weighted path and exactly compute the expected size of the resultant residual set.

LA - eng

KW - total acquisition number; Poissonization; dePoissonization; Maxwell-Boltzman and Bose-Einstein allocation.

UR - http://eudml.org/doc/288291

ER -

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.