Questions tagged [online-algorithms]
Questions about algorithms that receive the input piecewise and have to make decisions, that is produce output, before having seen the whole input.
62
questions
3
votes
0answers
607 views
Motion planning using second order Bézier curves
I'm trying to find an algorithm for a motion planning problem. I have $N$ points, $P_1$ to $P_N$, in $k$-dimensional cartesian space, defining $N-1$ segments. The problem is about constructing the ...
3
votes
0answers
77 views
Online algorithm for planning
Let S be a system whose state can be altered by performing actions. Each action has two possible outcomes, and each outcome brings to a specific system state. A ...
16
votes
1answer
288 views
Can a perceptron forget?
I would like to build an online web-based machine learning system, where users can continuously add classified samples, and have the model updated online. I would like to use a perceptron or a similar ...
2
votes
1answer
2k views
Load balancing. Why not use priority queues?
I have recently learned about various randomized algorithms for load balancing. The model is always that there are $m$ balls and $n$ bins and the balls arrive one at a time. The task is to minimize ...
1
vote
1answer
114 views
How to sample uniformly from a stream of elements, some of which are unsuited?
I get values $x_t$ in an online fashion and want to buy "good" ones, where "good" means that some measure $P(x_t) >T$. Consider the following simple algorithm.
...
11
votes
2answers
540 views
Fair cake-cutting when players join late
The usual statement of the fair cake-cutting problem assumes that all $n$ players get their share at the same time. However, in many cases the players arrive incrementally. For example, we may divide ...
19
votes
1answer
696 views
Weighted sum of last N numbers
Suppose we're receiving numbers in a stream. After each number is received, a weighted sum of the last $N$ numbers needs to be calculated, where the weights are always the same, but arbitrary.
How ...
19
votes
2answers
2k views
Computing inverse matrix when an element changes
Given an $n \times n$ matrix $\mathbf{A}$. Let the inverse matrix of $\mathbf{A}$ be $\mathbf{A}^{-1}$ (that is, $\mathbf{A}\mathbf{A}^{-1} = \mathbf{I}$). Assume that one element in $\mathbf{A}$ is ...
1
vote
0answers
561 views
Streaming Knapsack Problem
I want to implement efficiently "streaming Knapsack" problem in java.
The problem is I have a stream input of integer data coming continuously for example -1, 2, 9, 5, 5, 11, 1 -3,...
The question ...
15
votes
3answers
3k views
Determine missing number in data stream
We receive a stream of $n-1$ pairwise different numbers from the set $\left\{1,\dots,n\right\}$.
How can I determine the missing number with an algorithm that reads the stream once and uses a memory ...
3
votes
1answer
61 views
Block detection in repeated stream
I need to recover a data block from a repeated stream of data. I'm looking to see what algorithms may already exist for this as it does not feel like a novel situation.
Here are the specifics:
There ...
4
votes
2answers
704 views
Online generation of uniform samples
A source provides a stream of items $x_1, x_2,\dots$ . At each step $n$ we want to save a random sample $S_n \subseteq \{ (x_i, i)|1 \le i \le n\}$ of size $k$, i.e. $S_n$ should be a uniformly chosen ...
