On-Line Difference Maximization
| dc.creator | Kao, Ming-Yang | |
| dc.creator | Tate, Stephen R. | |
| dc.date | 2001-01-23 | |
| dc.date | 2001-01-24 | |
| dc.date.accessioned | 2026-07-07T03:16:53Z | |
| dc.date.available | 2026-07-07T03:16:53Z | |
| dc.description | 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^2/8-Θ(n\log n). An analysis shows that the optimal expected off-line gain is n^2/6+Θ(1), so the performance of our on-line algorithm is within a factor of 3/4 of the best off-line strategy. | |
| dc.identifier | https://arxiv.org/abs/cs/0101024 | |
| dc.identifier | http://arxiv.org/abs/cs/0101024 | |
| dc.identifier | SIAM Journal on Discrete Mathematics, 12(1):78-90, 1999 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/30519 | |
| dc.subject | Data Structures and Algorithms | |
| dc.subject | Discrete Mathematics | |
| dc.subject | F.2.2; G.1.6; G.2.1; G.2.3; G.3 | |
| dc.title | On-Line Difference Maximization | |
| dc.type | text |