Minimizing the total completion time on-line on a single machine, using restarts

R. Stee, van; J.A. Poutré, la

doi:10.1016/j.jalgor.2004.10.001

Minimizing the total completion time on-line on a single machine, using restarts

R. Stee, van
, J.A. Poutré, la

Information Systems IE&IS

Research output: Contribution to journal › Article › Academic › peer-review

19 Citations (Scopus)

Abstract

We give an algorithm to minimize the total completion time on-line on a single machine, using restarts, with a competitive ratio of 3/2. The optimal competitive ratio without using restarts is 2 for deterministic algorithms and e/(e-1) ˜ 1.582 for randomized algorithms. This is the first restarting algorithm to minimize the total completion time that is proved to be better than an algorithm that does not restart.

Original language	English
Pages (from-to)	95-129
Journal	Journal of Algorithms
Volume	57
Issue number	2
DOIs	https://doi.org/10.1016/j.jalgor.2004.10.001
Publication status	Published - 2005

Access to Document

10.1016/j.jalgor.2004.10.001

Cite this

@article{890375524c294e6791fb8d25a14e2c62,

title = "Minimizing the total completion time on-line on a single machine, using restarts",

abstract = "We give an algorithm to minimize the total completion time on-line on a single machine, using restarts, with a competitive ratio of 3/2. The optimal competitive ratio without using restarts is 2 for deterministic algorithms and e/(e-1) ˜ 1.582 for randomized algorithms. This is the first restarting algorithm to minimize the total completion time that is proved to be better than an algorithm that does not restart.",

author = "\{Stee, van\}, R. and \{Poutr{\'e}, la\}, J.A.",

year = "2005",

doi = "10.1016/j.jalgor.2004.10.001",

language = "English",

volume = "57",

pages = "95--129",

journal = "Journal of Algorithms",

issn = "0196-6774",

publisher = "Academic Press Inc.",

number = "2",

}

TY - JOUR

T1 - Minimizing the total completion time on-line on a single machine, using restarts

AU - Stee, van, R.

AU - Poutré, la, J.A.

PY - 2005

Y1 - 2005

N2 - We give an algorithm to minimize the total completion time on-line on a single machine, using restarts, with a competitive ratio of 3/2. The optimal competitive ratio without using restarts is 2 for deterministic algorithms and e/(e-1) ˜ 1.582 for randomized algorithms. This is the first restarting algorithm to minimize the total completion time that is proved to be better than an algorithm that does not restart.

AB - We give an algorithm to minimize the total completion time on-line on a single machine, using restarts, with a competitive ratio of 3/2. The optimal competitive ratio without using restarts is 2 for deterministic algorithms and e/(e-1) ˜ 1.582 for randomized algorithms. This is the first restarting algorithm to minimize the total completion time that is proved to be better than an algorithm that does not restart.

U2 - 10.1016/j.jalgor.2004.10.001

DO - 10.1016/j.jalgor.2004.10.001

M3 - Article

SN - 0196-6774

VL - 57

SP - 95

EP - 129

JO - Journal of Algorithms

JF - Journal of Algorithms

IS - 2

ER -

Minimizing the total completion time on-line on a single machine, using restarts

Abstract

Access to Document

Fingerprint

Cite this