### Skapa referens, olika format (klipp och klistra)

**Harvard**

Damaschke, P., Ha, P. och Tsigas, P. (2005) *One-Way Trading with Time-Varying Exchange Rate Bounds*. Göteborg : Chalmers University of Technology (Technical report - Department of Computer Science and Engineering, Chalmers University of Technology and Göteborg University, nr: 2005:17).

** BibTeX **

@techreport{

Damaschke2005,

author={Damaschke, Peter and Ha, Phuong and Tsigas, Philippas},

title={One-Way Trading with Time-Varying Exchange Rate Bounds},

abstract={One-way trading is a basic online problem in finance. Since its optimal solution is given by a simple formula (however with difficult analysis), the problem is attractive as a target to which other practical online problems can be
transformed. However, there are still natural online problems that do not fit in the known variants of one-way trading. We present some new models where the bounds of exchange rates are not constant but vary with time in certain ways. The first model, where the (logarithmic) exchange rate has limited decay speed, arises from an issue in distributed data structures, namely to maximize the
(appropriately defined) freshness of values in concurrent objects. For this model we prove a lower bound on the competitive ratio which is nearly optimal, i.e., up
to a small constant factor. Clearly, the lower bound holds also against stronger adversaries. Then, we give an optimal algorithm in a model where only the maximal allowed exchange rate decreases with time, but the actual exchange rates may jump arbitrarily within this frame. We have chosen this more powerful adversary model afterwards because some applications does not make use of the limited decay speed. In fact, we adapt the optimal threat-based algorithm of El-Yaniv et al. (2001) to our case. Our numerical experiments suggest that this algorithm is still not too far from the lower bound for the weaker adversary. This is
explained by the observation that slowly increasing exchange rates seem to be the worst case for the online player.},

publisher={Chalmers University of Technology},

place={Göteborg},

year={2005},

series={Technical report - Department of Computer Science and Engineering, Chalmers University of Technology and Göteborg University, no: 2005:17},

keywords={algorithms and data structures, distributed computing, online algorithms, one-way trading},

note={14},

}

** RefWorks **

RT Report

SR Print

ID 7608

A1 Damaschke, Peter

A1 Ha, Phuong

A1 Tsigas, Philippas

T1 One-Way Trading with Time-Varying Exchange Rate Bounds

YR 2005

AB One-way trading is a basic online problem in finance. Since its optimal solution is given by a simple formula (however with difficult analysis), the problem is attractive as a target to which other practical online problems can be
transformed. However, there are still natural online problems that do not fit in the known variants of one-way trading. We present some new models where the bounds of exchange rates are not constant but vary with time in certain ways. The first model, where the (logarithmic) exchange rate has limited decay speed, arises from an issue in distributed data structures, namely to maximize the
(appropriately defined) freshness of values in concurrent objects. For this model we prove a lower bound on the competitive ratio which is nearly optimal, i.e., up
to a small constant factor. Clearly, the lower bound holds also against stronger adversaries. Then, we give an optimal algorithm in a model where only the maximal allowed exchange rate decreases with time, but the actual exchange rates may jump arbitrarily within this frame. We have chosen this more powerful adversary model afterwards because some applications does not make use of the limited decay speed. In fact, we adapt the optimal threat-based algorithm of El-Yaniv et al. (2001) to our case. Our numerical experiments suggest that this algorithm is still not too far from the lower bound for the weaker adversary. This is
explained by the observation that slowly increasing exchange rates seem to be the worst case for the online player.

PB Chalmers University of Technology

T3 Technical report - Department of Computer Science and Engineering, Chalmers University of Technology and Göteborg University, no: 2005:17

LA eng

OL 30