On the on-line number of snacks problem

Weimin Ma, Jia You, Yinfeng Xu, James Liu, Kanliang Wang

Research output: Journal article publicationJournal articleAcademic researchpeer-review

18 Citations (Scopus)

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σ:CA(σ)/COPT(σ), where σ denotes a sequence of numbers of customers, COPT(σ) is the cost of satisfying σ by an optimal off-line algorithm, and CA(σ) 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.
Original languageEnglish
Pages (from-to)449-462
Number of pages14
JournalJournal of Global Optimization
Volume24
Issue number4
DOIs
Publication statusPublished - 1 Dec 2002

Keywords

  • Competitive algorithms
  • Competitive ratio
  • On-line number of snacks problem

ASJC Scopus subject areas

  • Computer Science Applications
  • Control and Optimization
  • Management Science and Operations Research
  • Applied Mathematics

Cite this