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 Citation (Scopus)

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

Stochastic Games
Optimal Algorithm
Maximise
Distinct
Arbitrary
Strategy

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.
Kao, Ming Yang ; Tate, Stephen R. / On-line difference maximization. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms. editor / Anon. ACM, 1997. pp. 175-182
@inproceedings{a13d3d2a996043678b2ee6cc165ec67c,
title = "On-line difference maximization",
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.",
author = "Kao, {Ming Yang} and Tate, {Stephen R.}",
year = "1997",
month = "1",
day = "1",
language = "English (US)",
pages = "175--182",
editor = "Anon",
booktitle = "Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms",
publisher = "ACM",

}

Kao, MY & Tate, SR 1997, On-line difference maximization. in Anon (ed.), Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms. ACM, pp. 175-182, Proceedings of the 1996 8th Annual ACM-SIAM Symposium on Discrete Algorithms, New Orleans, LA, USA, 1/5/97.

On-line difference maximization. / Kao, Ming Yang; Tate, Stephen R.

Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms. ed. / Anon. ACM, 1997. p. 175-182.

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

TY - GEN

T1 - On-line difference maximization

AU - Kao, Ming Yang

AU - Tate, Stephen R.

PY - 1997/1/1

Y1 - 1997/1/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0030778015&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0030778015&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:0030778015

SP - 175

EP - 182

BT - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

A2 - Anon, null

PB - ACM

ER -

Kao MY, Tate SR. On-line difference maximization. In Anon, editor, Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms. ACM. 1997. p. 175-182