Talk:Online algorithm

From Wikipedia, the free encyclopedia

[edit] Super-online?

Is there a word for an online algorithm that has the additional property that partial results can be combined? That is, if I want to run an algorithm in parallel, I want to be able to combine partial results. For example, the sum of a set of numbers is the sum of the partial sums. —Ben FrantzDale 01:00, 7 December 2006 (UTC)

Hi Ben,

1). This might be a stretch of your question... If you had a program that could determine the competitiveness of a randomized algorithm against any adaptive online adversary on one processor and you used a different processor to find the competitiveness of the algorithm against any oblivious adversary, then you could combine these results using Thm 2.2 from:

S. Ben-David, A. Borodin, R. Karp, G. Tardos, A. Wigderson. (1994). "On the Power of Randomization in On-line Algorithms". Algorithmica 11: 5-6.

Thm 2.2 states: If G is a c-competitive randomized algorithm against any adaptive online adversary, and there is a randomized d-competitive algorithm against any oblivious adversary, then G is a randomized (c * d)-competitive algorithm against any adaptive offline adversary.

2). Your question sounds more like a practical question compared a theoretical question. If you can give an example of such a problem you are talking about, perhaps I can give additional information.

Hope this helps,

Oravec 04:03, 7 December 2006 (UTC)

A very slightly more complicated example is computing an average. You can keep track of a sum and a count and can combine two partial results by adding the sum and the count. A more complicated example is computing the standard deviation of a bunch of numbers. It is definately possible to compute this as an online algorithm, as shown in Algorithms for calculating variance. The internal state of that algorithm is a count, the current mean, and the current sample variance. From that page, though, it isn't clear how you would combine partial results. Obviously it's easy to combine the sum and means, but it isn't obvious how you'd combine the variances.

In general I'm just interested in O(N) algorithms that have O(1) internal state but where the internal state for partial results can be combined so each of m processors could compute a partial result in O(N/m) time and those results could then be combined quickly to get the full solution. —Ben FrantzDale 05:01, 7 December 2006 (UTC)