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

**Harvard**

Damaschke, P., Tsigas, P. och Ha, P. (2009) *Online search with time-varying price bounds*.

** BibTeX **

@article{

Damaschke2009,

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

title={Online search with time-varying price bounds},

journal={Algorithmica},

issn={0178-4617 },

volume={55},

issue={4},

pages={619-642},

abstract={Online search is a basic online problem. The fact that its optimal deterministic/randomized solutions are given by simple formulas (however with difficult analysis) makes the problem attractive as a target to which other practical online problems can be transformed to find optimal solutions. However, since the upper/lower bounds of prices in available models are constant, natural online problems in which these bounds vary with time do not fit in the available models. We present two new models where the bounds of prices are not constant but vary with time in certain ways. The first model, where the upper and lower bounds of (logarithmic) prices have decay speed, arises from a problem in concurrent data structures, namely to maximize the (appropriately defined) freshness of data in concurrent objects. For this model we present an optimal deterministic algorithm and a nearly-optimal randomized algorithm. We also prove a lower bound of competitive ratios of randomized algorithms. The second model is inspired by the fact that some applications do not utilize the decay speed of the lower bound of prices in the first model. In the second model, only the upper bound decreases arbitrarily with time and the lower bound is constant. Clearly, the lower bound of competitive ratios proved for the first model holds also against the stronger adversary in the second model. For the second model, we present an optimal randomized algorithm. Our numerical experiments on the freshness problem show that this new algorithm achieves much better/smaller competitive ratios than previous algorithms do.},

year={2009},

keywords={search algorithms, online algorithms, competitive analysis, game theory},

}

** RefWorks **

RT Journal Article

SR Print

ID 97554

A1 Damaschke, Peter

A1 Tsigas, Philippas

A1 Ha, Phuong

T1 Online search with time-varying price bounds

YR 2009

JF Algorithmica

SN 0178-4617

VO 55

IS 4

SP 619

OP 642

AB Online search is a basic online problem. The fact that its optimal deterministic/randomized solutions are given by simple formulas (however with difficult analysis) makes the problem attractive as a target to which other practical online problems can be transformed to find optimal solutions. However, since the upper/lower bounds of prices in available models are constant, natural online problems in which these bounds vary with time do not fit in the available models. We present two new models where the bounds of prices are not constant but vary with time in certain ways. The first model, where the upper and lower bounds of (logarithmic) prices have decay speed, arises from a problem in concurrent data structures, namely to maximize the (appropriately defined) freshness of data in concurrent objects. For this model we present an optimal deterministic algorithm and a nearly-optimal randomized algorithm. We also prove a lower bound of competitive ratios of randomized algorithms. The second model is inspired by the fact that some applications do not utilize the decay speed of the lower bound of prices in the first model. In the second model, only the upper bound decreases arbitrarily with time and the lower bound is constant. Clearly, the lower bound of competitive ratios proved for the first model holds also against the stronger adversary in the second model. For the second model, we present an optimal randomized algorithm. Our numerical experiments on the freshness problem show that this new algorithm achieves much better/smaller competitive ratios than previous algorithms do.

LA eng

DO 10.1007/s00453-007-9156-9

OL 30