Please use this identifier to cite or link to this item:
Title: On the on-line number of snacks problem
Authors: Ma, W
You, J 
Xu, Y
Liu, J
Wang, K
Keywords: Competitive algorithms
Competitive ratio
On-line number of snacks problem
Issue Date: 2002
Publisher: Kluwer Academic Publ
Source: Journal of Global Optimization, 2002, v. 24, no. 4, p. 449-462 How to cite?
Journal: Journal of global optimization 
Abstract: In the number of snacks problem (NSP), which was originally proposed by our team, an on-line player is given the task of deciding how many shares of snacks his noshery should prepare each day. The on-line player must make his decision and then finish the preparation before the customers come to his noshery for the snacks; in other words, he must make decision in an on-line fashion. His goal is to minimize the competitive ratio, defined as σ: C A(σ)/C OPT(σ), where σ denotes a sequence of numbers of customers, C OPT(σ) is the cost of satisfying σ by an optimal off-line algorithm, and C A(σ) is the cost of satisfying σ by an on-line algorithm. In this paper we give a competitive algorithm for on-line number of snacks problem P1, the Extreme Numbers Harmonic Algorithm(ENHA), with competitive ratio 1+pċ(M-m)/(M+m), where M and m are two extreme numbers of customers over the total period of the game, and p is a ratio concerning the cost of the two types of situations, and then prove that this competitive ratio is the best one if an on-line player chooses a fixed number of shares of snacks for any sequence of numbers of customers. We also discuss several variants of the NSP and give some results for it. Finally, we propose a conjecture for the on-line NSP.
ISSN: 0925-5001
EISSN: 1573-2916
DOI: 10.1023/A:1021253103047
Appears in Collections:Journal/Magazine Article

View full-text via PolyU eLinks SFX Query
Show full item record


Last Week
Last month
Citations as of Aug 10, 2018


Last Week
Last month
Citations as of Jul 24, 2018

Page view(s)

Last Week
Last month
Citations as of Aug 13, 2018

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.