On-line difference maximization

Ming Yang Kao; Stephen R. Tate

On-line difference maximization

Ming Yang Kao^*, Stephen R. Tate

^*Corresponding author for this work

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference 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 language	English (US)
Title of host publication	Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
Editors	Anon
Publisher	ACM
Pages	175-182
Number of pages	8
State	Published - Jan 1 1997
Event	Proceedings of the 1996 8th Annual ACM-SIAM Symposium on Discrete Algorithms - New Orleans, LA, USA Duration: Jan 5 1997 → Jan 7 1997

Other

Other	Proceedings of the 1996 8th Annual ACM-SIAM Symposium on Discrete Algorithms
City	New Orleans, LA, USA
Period	1/5/97 → 1/7/97

ASJC Scopus subject areas

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

Cite this

@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 = jan,

day = "1",

language = "English (US)",

pages = "175--182",

editor = "Anon",

booktitle = "Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms",

publisher = "ACM",

note = "Proceedings of the 1996 8th Annual ACM-SIAM Symposium on Discrete Algorithms ; Conference date: 05-01-1997 Through 07-01-1997",

}

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

T2 - Proceedings of the 1996 8th Annual ACM-SIAM Symposium on Discrete Algorithms

Y2 - 5 January 1997 through 7 January 1997

ER -

On-line difference maximization

Abstract

Other

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this