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

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. 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
PublisherACM
Pages175-182
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

Other

OtherProceedings of the 1996 8th Annual ACM-SIAM Symposium on Discrete Algorithms
CityNew Orleans, LA, USA
Period1/5/971/7/97

    Fingerprint

ASJC Scopus subject areas

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

Cite this

Kao, M. Y., & Tate, S. R. (1997). On-line difference maximization. In Anon (Ed.), Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 175-182). ACM.