کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4648449 | 1342412 | 2012 | 10 صفحه PDF | دانلود رایگان |

“The Baron’s Omni-sequence”, first defined by Khovanova and Lewis (2011) [5], is a sequence that gives for each nn the minimum number of weighings on balance scales that can verify the correct labeling of nn identically-looking coins with distinct integer weights between 1 gram and ngrams.In [5], Khovanova and Lewis provide upper and lower bounds for this sequence, where the upper bound follows from the use of a particular algorithmic scheme. We continue this investigation by providing new algorithms that provide better upper bounds, within a factor of 22 from the lower bounds (improving on Khovanova and Lewis’s 2.962.96). Furthermore, we show that these new algorithms are, under certain criteria, optimal within the framework of the present algorithmic scheme. We also discuss directions that may provide improvements within or over the scheme.
Journal: Discrete Mathematics - Volume 312, Issue 7, 6 April 2012, Pages 1326–1335