OPTIMAL ONLINE ALGORITHM FOR METRICAL TASK SYSTEMS.

Allan Borodin; Nathan Linial Nathan; Michael Saks

doi:10.1145/28395.28435

OPTIMAL ONLINE ALGORITHM FOR METRICAL TASK SYSTEMS.

Allan Borodin, Nathan Linial Nathan, Michael Saks

Research output: Contribution to journal › Conference article › peer-review

60 Scopus citations

Abstract

In practice, almost all dynamic systems require decisions to be made online, without full knowledge of their future impact on the system. We introduce a general model for the processing of sequences of tasks and develop a general online decision algorithm. We show that, for an important class of special cases, this algorithm is optimal among all online algorithms.

Original language	English (US)
Pages (from-to)	373-382
Number of pages	10
Journal	Conference Proceedings of the Annual ACM Symposium on Theory of Computing
DOIs	https://doi.org/10.1145/28395.28435
State	Published - 1987
Externally published	Yes

All Science Journal Classification (ASJC) codes

Software

Access to Document

10.1145/28395.28435

Cite this

@article{19c855d40ea446dda11947dd53c10171,

title = "OPTIMAL ONLINE ALGORITHM FOR METRICAL TASK SYSTEMS.",

abstract = "In practice, almost all dynamic systems require decisions to be made online, without full knowledge of their future impact on the system. We introduce a general model for the processing of sequences of tasks and develop a general online decision algorithm. We show that, for an important class of special cases, this algorithm is optimal among all online algorithms.",

author = "Allan Borodin and {Linial Nathan}, Nathan and Michael Saks",

year = "1987",

doi = "10.1145/28395.28435",

language = "English (US)",

pages = "373--382",

journal = "Conference Proceedings of the Annual ACM Symposium on Theory of Computing",

issn = "0734-9025",

publisher = "Association for Computing Machinery (ACM)",

}

TY - JOUR

T1 - OPTIMAL ONLINE ALGORITHM FOR METRICAL TASK SYSTEMS.

AU - Borodin, Allan

AU - Linial Nathan, Nathan

AU - Saks, Michael

PY - 1987

Y1 - 1987

N2 - In practice, almost all dynamic systems require decisions to be made online, without full knowledge of their future impact on the system. We introduce a general model for the processing of sequences of tasks and develop a general online decision algorithm. We show that, for an important class of special cases, this algorithm is optimal among all online algorithms.

AB - In practice, almost all dynamic systems require decisions to be made online, without full knowledge of their future impact on the system. We introduce a general model for the processing of sequences of tasks and develop a general online decision algorithm. We show that, for an important class of special cases, this algorithm is optimal among all online algorithms.

UR - http://www.scopus.com/inward/record.url?scp=0023545513&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0023545513&partnerID=8YFLogxK

U2 - 10.1145/28395.28435

DO - 10.1145/28395.28435

M3 - Conference article

AN - SCOPUS:0023545513

SN - 0734-9025

SP - 373

EP - 382

JO - Conference Proceedings of the Annual ACM Symposium on Theory of Computing

JF - Conference Proceedings of the Annual ACM Symposium on Theory of Computing

ER -

OPTIMAL ONLINE ALGORITHM FOR METRICAL TASK SYSTEMS.

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this