On-Line Difference Maximization

UNCG Author/Contributor (non-UNCG co-authors, if there are any, appear on document)
Stephen R. Tate, Professor and Department Head (Creator)
Institution
The University of North Carolina at Greensboro (UNCG )
Web Site: http://library.uncg.edu/

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 o ff-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 o -line gain is n2=6 + Θ(1), so the performance of our on-line algorithm is within a factor of 3=4 of the best o -line strategy.

Additional Information

Publication
SIAM Journal on Discrete Math 12(1), 78-90
Language: English
Date: 1999
Keywords
Analysis of algorithms, On-line algorithms, Financial games, Secretary problem

Email this document to