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

**Harvard**

Damaschke, P. (2003) *Nearly optimal strategies for special cases of on-line capital investment*.

** BibTeX **

@article{

Damaschke2003,

author={Damaschke, Peter},

title={Nearly optimal strategies for special cases of on-line capital investment},

journal={Theoretical Computer Science},

issn={0304-3975},

volume={302},

issue={1},

pages={35-44},

abstract={Suppose that some job must be done for a period of unspecified duration. The market offers a selection of devices that can do this job, each characterized by
purchase and running costs. Which of them should we buy at what times, in order to minimize the total costs? As usual in competitive analysis, the cost of an on-line solution is compared to the optimum costs paid by a clearvoyant buyer. This problem which generalizes the basic rent-to-buy
problem has been introduced by Y. Azar et al. In the so-called convex case where lower running costs always
imply higher prices, a strategy with competitive ratio
6.83 has been proposed. Here we consider two natural
subcases of the convex case in a continuous-time model
where new devices can be bought at any time. For the
static case where all devices are available at the beginning, we give a simple 4-competitive deterministic
algorithm, and we show that 3.618 is a lower bound. (This
is also the first non-trivial lower bound for the convex case, both for discrete and continuous time.) Furthermore
we give a 2.88-competitive randomized algorithm. In the
case that all devices have equal prices but are not all available at the beginning, we show that a very simple algorithm is 2-competitive, and we derive a 1.618
lower bound.},

year={2003},

keywords={on-line problems, competitive ratio, rent-to-buy},

}

** RefWorks **

RT Journal Article

SR Electronic

ID 1763

A1 Damaschke, Peter

T1 Nearly optimal strategies for special cases of on-line capital investment

YR 2003

JF Theoretical Computer Science

SN 0304-3975

VO 302

IS 1

SP 35

OP 44

AB Suppose that some job must be done for a period of unspecified duration. The market offers a selection of devices that can do this job, each characterized by
purchase and running costs. Which of them should we buy at what times, in order to minimize the total costs? As usual in competitive analysis, the cost of an on-line solution is compared to the optimum costs paid by a clearvoyant buyer. This problem which generalizes the basic rent-to-buy
problem has been introduced by Y. Azar et al. In the so-called convex case where lower running costs always
imply higher prices, a strategy with competitive ratio
6.83 has been proposed. Here we consider two natural
subcases of the convex case in a continuous-time model
where new devices can be bought at any time. For the
static case where all devices are available at the beginning, we give a simple 4-competitive deterministic
algorithm, and we show that 3.618 is a lower bound. (This
is also the first non-trivial lower bound for the convex case, both for discrete and continuous time.) Furthermore
we give a 2.88-competitive randomized algorithm. In the
case that all devices have equal prices but are not all available at the beginning, we show that a very simple algorithm is 2-competitive, and we derive a 1.618
lower bound.

LA eng

DO 10.1016/S0304-3975(02)00727-2

LK http://dx.doi.org/10.1016/S0304-3975(02)00727-2

OL 30