Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/19085
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.
URI: http://hdl.handle.net/10397/19085
ISSN: 0925-5001
EISSN: 1573-2916
DOI: 10.1023/A:1021253103047
Appears in Collections:Journal/Magazine Article

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

SCOPUSTM   
Citations

17
Last Week
0
Last month
0
Citations as of Jul 31, 2017

WEB OF SCIENCETM
Citations

16
Last Week
0
Last month
0
Citations as of Aug 14, 2017

Page view(s)

48
Last Week
2
Last month
Checked on Aug 14, 2017

Google ScholarTM

Check

Altmetric



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