Back to Search
Start Over
ON-LINE DIFFERENCE MAXIMIZATION.
- Source :
- SIAM Journal on Discrete Mathematics; 1999, Vol. 12 Issue 1, p78-90, 13p
- Publication Year :
- 1999
-
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 off-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 n²/8 - Θ(n log n). An analysis shows that the optimal expected off-line gain is n²/6 + Θ(1), so the performance of our on-line algorithm is within a factor of 3/4 of the best off-line strategy. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 08954801
- Volume :
- 12
- Issue :
- 1
- Database :
- Complementary Index
- Journal :
- SIAM Journal on Discrete Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 13220136
- Full Text :
- https://doi.org/10.1137/S0895480196307445