Open AccessReasoning about online algorithms with weighted automata
Author(s) -
Benjamin Aminof,
Orna Kupferman,
Robby Lampert
Publication year - 2010
Publication title -
acm transactions on algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.093
H-Index - 57
eISSN - 1549-6333
pISSN - 1549-6325
DOI - 10.1145/1721837.1721844
Subject(s) - automaton , competitive analysis , computer science , determinism , online algorithm , algorithm , theoretical computer science , word (group theory) , mathematics , upper and lower bounds , mathematical analysis , physics , geometry , quantum mechanics
We describe an automata-theoretic approach for the compet- itive analysis of online algorithms. Our approach is based on weighted automata, which assign to each input word a cost in IR¸0. By relating the "unbounded look ahead" of op- timal offline algorithms with nondeterminism, and relating the "no look ahead" of online algorithms with determinism, we are able to solve problems about the competitive ratio of online algorithms, and the memory they require, by reducing them to questions about determinization and approximated determinization of weighted automata.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom