On-line difference maximization

Ming Yang Kao*, Stephen R. Tate

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

9 Scopus citations

Abstract

In this paper we examine problems motivated by on-line financial problems and stochastic games. In particular, we consider a sequence of entirely arbitrary distinct values arriving in random order, and must devise strategies for selecting low values followed by high values in such a way as to maximize the expected gain in rank from low values to high values. First, we consider a scenario in which only one low value and one high value may be selected. We give an optimal on-line algorithm for this scenario, and analyze it to show that, surprisingly, the expected gain is n - O(1), and so differs from the best possible off-line gain by only a constant additive term (which is, in fact, fairly small - at most 15). In a second scenario, we allow multiple nonoverlapping low/high selections, where the total gain for our algorithm is the sum of the individual pair gains. We also give an optimal on-line algorithm for this problem, where the expected gain is n2/8 - ⊖(n log n). An analysis shows that the optimal expected off-line gain is n2/6 + ⊖(1), so the performance of our on-line algorithm is within a factor of 3/4 of the best off-line strategy.

Original languageEnglish (US)
Pages (from-to)78-90
Number of pages13
JournalSIAM Journal on Discrete Mathematics
Volume12
Issue number1
DOIs
StatePublished - 1999

Keywords

  • Analysis of algorithms
  • Financial games
  • On-line algorithms
  • Secretary problem

ASJC Scopus subject areas

  • Mathematics(all)

Fingerprint Dive into the research topics of 'On-line difference maximization'. Together they form a unique fingerprint.

Cite this