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.
On-Line Difference Maximization
PDF (Portable Document Format)
449 KB
Created on 3/14/2011
Views: 1854
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