On-line difference maximization

Ming Yang Kao*, Stephen R. Tate

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations


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. We give optimal algorithms for this problem, and provide tight analysis of their performance.

Original languageEnglish (US)
Title of host publicationProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
Editors Anon
Number of pages8
StatePublished - Jan 1 1997
EventProceedings of the 1996 8th Annual ACM-SIAM Symposium on Discrete Algorithms - New Orleans, LA, USA
Duration: Jan 5 1997Jan 7 1997


OtherProceedings of the 1996 8th Annual ACM-SIAM Symposium on Discrete Algorithms
CityNew Orleans, LA, USA

ASJC Scopus subject areas

  • Chemical Health and Safety
  • Software
  • Safety, Risk, Reliability and Quality
  • Discrete Mathematics and Combinatorics


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

Cite this