Questions about algorithms that receive the input piecewise and have to make decisions, that is produce output, before having seen the whole input.

learn more… | top users | synonyms

4
votes
2answers
157 views

Data structure for sparse matrices for an online problem

I need to compute a large linear optimization problem very often after recieving updates to my optimization problem. That is I have a linear problem to find an x such that $x_1 * c_1 + ... + x_n * ...
0
votes
1answer
38 views

Online supervised learning algorithm

I have labeled examples coming in on the fly, thus I need to create a classifier from sequential data instead of a static example set. Incoming data is fully labeled, there are no unlabeled examples. ...
1
vote
1answer
75 views

Keep k+ties largest elements in a stream

I have $n$ numbers that come one by one, and when the last element comes, I want to output $k$ largest elements and those that are ties with the minimal element from this top-$k$ element. For ...
1
vote
1answer
31 views

Online and parallizeable set intersection algorithm

I have problem that is reducible to the following: From a collection of stacks, find all items whose "keys" are on all stacks. My current solution to this problem is to just pop things off as ...
4
votes
2answers
103 views

Lazily computing a random permutation of the positive integers

Are there any existing efficient algorithms for lazily computing a random permutation of the positive integers in a given range (e.g. the range offered by an unsigned integer type in a CPU)? What I ...
3
votes
1answer
28 views

Packing unsplittable flows problem

For a single stream of elements as input every elements should be routed into a fixed number of $k$ output streams trying to keep them balanced. In the following example $k=3$ : Let's define as ...
2
votes
0answers
31 views

Do online quantile estimation algorithms that support deletions exist?

There are several online quantile estimation algorithms, but I haven't seen any that supports deletions (i.e. unobserve elements observed in the past). Are there any such known algorithms? To ...
3
votes
1answer
217 views

An incrementally-condensed transitive-reduction of a DAG, with efficient reachability queries

Is there an incremental directed graph data structure that has the following properties: Keeps an internal graph structure as a DAG, and the graph is accessible (notwithstanding other helper ...
2
votes
0answers
235 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
58 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 ...
15
votes
1answer
177 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 ...
1
vote
1answer
481 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
79 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. ...
9
votes
2answers
281 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 ...
16
votes
1answer
356 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 ...
13
votes
2answers
523 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
282 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 ...
10
votes
3answers
857 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
45 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: ...
4
votes
1answer
232 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 ...