NDLI: An optimal online algorithm for metrical task systems

Please wait, while we are loading the content...

Matrix multiplication via arithmetic progressions

Solving minimum-cost flow problems by successive approximation

A new approach to all pairs shortest paths in planar graphs

An algorithm for linear programming which requires $O(((m+n)n^{2}+(m+n)^{1.5}n)L)$ arithmetic operations

A Linear time algorithm for computing the Voronoi diagram of a convex polygon

Testing for cycles in infinite graphs with periodic structure

Approximation algorithms for shortest path motion planning

The complexity of cutting convex polytypes

Algebraic methods in the theory of lower bounds for Boolean circuit complexity

Optimal bounds for decision problems on the CRCW PRAM

Two tapes are better than one for off-line Turing machines

Finite monoids and the fine structure of $NC^{1}$

The strong exponential hierarchy collapses

The Boolean formula value problem is in ALOGTIME

Deterministic simulation in LOGSPACE

Properties that characterize LOGCFL

Some consequences of the existence of pseudorandom generators

Efficiency considerations in using semi-random sources

Imperfect random sources and discrete controlled processes

The power of randomness for communication complexity

Towards a theory of software protection and simulation by oblivious RAMs

On hiding information from an oracle

The complexity of perfect zero-knowledge

Zero knowledge proofs of identity

How to play ANY mental game

Optimal distributed algorithms for minimum weight spanning tree, counting, leader election, and related problems

Analysis of backoff protocols for multiple access channels

Dynamic parallel complexity of computational circuits

Constructing disjoint paths on expander graphs

Reconfiguring a hypercube in the presence of faults

On the learnability of Boolean formulae

On learning Boolean functions

A model for hierarchical memory

Parallel symmetry-breaking in sparse graphs

A random NC algorithm for depth first search

A new graphy triconnectivity algorithm and its parallelization

Matching is as easy as matrix inversion

Fast parallel algorithms for chordal graphs

Two algorithms for maintaining order in a list

An optimal online algorithm for metrical task systems

Searching a two key table under a single key

The page number of genus g graphs is (g)

Simple algebras are difficult

Permutation groups in NC

Threshold spectra for random graphs

The decision problem for the probabilities of higher-order properties

Size-time complexity of Boolean networks for prefix computations

Single-factor Hensel lifting and its application to the straight-line complexity of certain polynomials

Realistic analysis of some randomized algorithms

Recognizing primes in random polynomial time

An optimal online algorithm for metrical task systems

Content Provider	ACM Digital Library
Author	Saks, M. Linial, N. Borodin, A.
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.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 O.) 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 state transition costs incurred.An online scheduling algorithm is one that chooses si only knowing T1 T2 … Ti. Such an algorithm operates within waste factor w if, on any input task sequence, its costs is within an additive constant of w times the optimal offline schedule cost. The online waste factor w(S, d) is the infirm waste factor of any online scheduling algorithm for (S, d). We show that w(S, d) = 2\|S\| - 1 for every task system in which d symmetric, and w(S, d) = &Ogr;(\|S\|2) for every task system.
Starting Page	373
Ending Page	382
Page Count	10
File Format	PDF
ISBN	0897912217
DOI	10.1145/28395.28435
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	1987-01-01
Publisher Place	New York
Access Restriction	Subscribed
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in