Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(9)
Competitive Analysis
Competitive Ratio
Dynamic System
Generic Model
Online Algorithm
Satisfiability
Scheduling Algorithm
State Transition
Triangle Inequality
Related Publications
(10)
Amortized efficiency of list update and paging rules
The 2Evader Problem
On algorithm design for metrical task systems
Probabilistic approximation of metric spaces and its algorithmic applications
An optimal online algorithm for metrical task systems
Subscribe
Academic
Publications
An optimal online algorithm for metrical task system
An optimal online algorithm for metrical task system,10.1145/146585.146588,Journal of The ACM,Allan Borodin,Nathan Linial,Michael E. Saks
Edit
An optimal online algorithm for metrical task system
(
Citations: 116
)
BibTex

RIS

RefWorks
Download
Allan Borodin
,
Nathan Linial
,
Michael E. Saks
In practice, almost all dynamic systems require decisions to be made online, without full knowledge of their future impact on the system. A general model for the processing of sequences of tasks is introduced, and a general online decision algorithm is developed. It is shown that, for an important class of special cases, this algorithm is optimal among all online algorithms.Specifically, a task system (S,d) for processing sequences of tasks consists of a set S of states and a cost matrix d where d(i, j is the cost of changing from state i to state j (we assume that d satisfies the
triangle inequality
and all diagonal entries are 0). The cost of processing a given task depends on the state of the system. A schedule for a sequence T1, T2,…, Tk of tasks is a sequence s1, s2,…,sk of states where si is the state in which Ti is processed; the cost of a schedule is the sum of all task processing costs and the
state transition
costs incurred.An online
scheduling algorithm
is one that chooses si only knowing T1T2…Ti. Such an algorithm is wcompetitive if, on any input task sequence, its cost is within an additive constant of w times the optimal offline schedule cost. The
competitive ratio
w(S, d) is the infimum w for which there is a wcompetitive online
scheduling algorithm
for (S,d). It is shown that w(S, d) = 2S–1 for every task system in which d is symmetric, and w(S, d) = O(S2) for every task system. Finally, randomized online scheduling algorithms are introduced. It is shown that for the uniform task system (in which d(i,j) = 1 for all i,j), the expected
competitive ratio
w¯(S,d) = O(logS).
Journal:
Journal of The ACM  JACM
, vol. 39, no. 4, pp. 745763, 1992
DOI:
10.1145/146585.146588
Cumulative
Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
(
portal.acm.org
)
(
portal.acm.org
)
(
doi.acm.org
)
(
www.cs.huji.ac.il
)
(
portal.acm.org
)
(
www.informatik.unitrier.de
)
More »
Citation Context
(33)
...Further, for “metrical task systems” [
33
]–[35], which generalize rentorbuy problems and the data center optimization problem, there are many algorithms available, but they typically have competitive ratios that are polylogarithmic in the number of servers...
Minghong Lin
,
et al.
Dynamic rightsizing for powerproportional data centers
...We build upon two wellstudied online problems, weighted paging/caching [1,21] and Metrical Task System (MTS) [4,
8
] (see our technical report [9] for details), and extend them to address two new challenges specific to our problem: (1) optimizing energy costs of executing batch jobs under timevarying electricity prices and job demand, and (2) balancing energy savings with bandwidth costs to minimize the total operation cost...
...Since our problem is a generalization of the MTS problem [
8
], we get a lower bound of Ω(log n) on the competitiveness of any online algorithm where n is the number of datacenters...
Niv Buchbinder
,
et al.
Online JobMigration for Reducing the Electricity Bill in the Cloud
...A metrical task system [26], [
27
] (MTS) is defined to be a pair (X;R) such that 1) X is a metric space...
...The Work Function Algorithm: For any metrical task system, (X;R), the work function algorithm [26], [
27
], [28] is defined as follows...
Eddy Caron
,
et al.
OnLine Optimization of Publish/Subscribe Overlays
...1.1 Problem Definitions and Preliminaries Metrical Task System (MTS) and Unfair MTS: The MTS problem was introduced by Borodin et al. [
6
] as a generalization of various online problems...
...Borodin et al. [
6
] gave a tight deterministic 2n 1 competitive algorithm for any metric, and a (log n)competitive randomized algorithm for the uniform metric...
Nikhil Bansal
,
et al.
Towards the Randomized kServer Conjecture: A PrimalDual Approach
...This is a concrete example of the metrical task system (MTS) problem, first introduced by Borodin, Linial and Saks [
1
]...
...Prior Work. Borodin, Linial and Saks [
1
] showed that the lower bound on the competitive ratio of any deterministic algorithm over any metric is 2n −1. They also designed an algorithm, the WorkFunction algorithm, that achieves exactly this bound...
...For the uniform case, Bartal, Linial and Saks [
1
] showed a lower bound on the competitive ratio for any algorithm of Hn ,t henth harmonic number...
...They [
1
] also designed an algorithm, Marking, that has competitive ratio2Hn...
...This paper focuses entirely on the construction of workbased algorithms, where the algorithm can forget about the sequence of cost vectors c 1 ,..., c t and simply use W t to choose p t . This algorithmic restriction has been used as early as [
1
] and appears...
...Here, the algorithm must choose a probability distributions p t ∈ Δn on each round t, and an adversary then chooses a loss vector l t ∈ [0,
1
] n .L etL t = � t=1 l s . Then the algorithm’s goal is to minimize...
Jacob Abernethy
,
et al.
A Regularization Approach to Metrical Task Systems
References
(28)
On the Power of Randomization in Online Algorithms (Extended Abstract)
(
Citations: 38
)
Shai Bendavid
,
Allan Borodin
,
Richard M. Karp
,
Gábor Tardos
,
Avi Wigderson
Conference:
ACM Symposium on Theory of Computing  STOC
, pp. 379386, 1990
Stochastic models in operations research
(
Citations: 373
)
D. P. Heyman
,
M. J. Sobel
Published in 1984.
A Strongly Competitive Randomized Paging Algorithm
(
Citations: 122
)
Lyle A. Mcgeoch
,
Daniel Dominic Sleator
Journal:
Algorithmica
, vol. 6, no. 6, pp. 816825, 1991
New results on server problems
(
Citations: 111
)
Marek Chrobak
,
Howard Karloff
,
Tom Payne
,
Sundar Vishwanathan
Conference:
ACMSIAM Symposium on Discrete Algorithms  SODA
, pp. 291300, 1990
Heuristics That Dynamically Organize Data Structures
(
Citations: 71
)
James R. Bitner
Journal:
Siam Journal on Computing  SIAMCOMP
, vol. 8, no. 1, pp. 82110, 1979
Sort by:
Citations
(116)
Dynamic rightsizing for powerproportional data centers
(
Citations: 1
)
Minghong Lin
,
Adam Wierman
,
Lachlan L. H. Andrew
,
Eno Thereska
Conference:
IEEE INFOCOM  INFOCOM
, pp. 10981106, 2011
Online computation with advice
Yuval Emek
,
Pierre Fraigniaud
,
Amos Korman
,
Adi Rosén
Journal:
Theoretical Computer Science  TCS
, vol. 412, no. 24, pp. 26422656, 2011
Online JobMigration for Reducing the Electricity Bill in the Cloud
Niv Buchbinder
,
Navendu Jain
,
Ishai Menache
Conference:
Networking  Networking
, pp. 172185, 2011
OnLine Optimization of Publish/Subscribe Overlays
Eddy Caron
,
Benjamin Depardon
,
Ajoy K. Datta
,
Lawrence L. Larmore
Published in 2011.
Towards the Randomized kServer Conjecture: A PrimalDual Approach
(
Citations: 4
)
Nikhil Bansal
,
Niv Buchbinder
Conference:
ACMSIAM Symposium on Discrete Algorithms  SODA
, pp. 4055, 2010