PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2017 | 37 | 4 | 919-934
Tytuł artykułu

The Total Acquisition Number Of The Randomly Weighted Path

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
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.
Wydawca
Rocznik
Tom
37
Numer
4
Strony
919-934
Opis fizyczny
Daty
wydano
2017-11-27
otrzymano
2015-08-14
poprawiono
2016-07-15
zaakceptowano
2016-07-15
online
2017-09-02
Bibliografia
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.doi-10_7151_dmgt_1972
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.