ZIB

Hits per page

hit 1 - 1 | 1 hit

Sorting

Electronic Resource

On the power of randomization in on-line algorithms (1994)

Ben-David, S. ; Borodin, A. ; Karp, R. ; [et al.]

Springer

Algorithmica 11 (1994), S. 2-14

add to mindlist on the mindlist

Details

ISSN: 1432-0541

Keywords: On-line algorithms ; Competitive analysis ; Randomized algorithms ; Game theory

Source: Springer Online Journal Archives 1860-2000

Topics: Computer Science , Mathematics

Notes: Abstract Against in adaptive adversary, we show that the power of randomization in on-line algorithms is severely limited! We prove the existence of an efficient “simulation” of randomized on-line algorithms by deterministic ones, which is best possible in general. The proof of the upper bound is existential. We deal with the issue of computing the efficient deterministic algorithm, and show that this is possible in very general cases.

Type of Medium: Electronic Resource

URL: http://dx.doi.org/10.1007/BF01294260

Permalink

Library	Location	Call Number	Volume/Issue/Year	Availability

Others were also interested in ...

Paper (German National Licenses)

Fulltext

hit 1 - 1 | 1 hit