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.
79
questions
2
votes
1
answer
239
views
Term for open-ended algorithms
There are some enumeration problems which have little input, except for some termination criterion. Examples for the question at hand would be
enumeration of prime numbers in ascending order
...
6
votes
2
answers
134
views
Online sorting without modifications
There is an array with $n$ places. There is a stream of $n$ unique numbers that arrive at a random order (permutation selected uniformly at random).
Whenever a number arrives, we must put it ...
3
votes
4
answers
8k
views
What is the fastest online sorting algorithm?
Quoting Online algorithm from Wikipedia:
In computer science, an online algorithm[1] is one that can process its input piece-by-piece in a serial fashion, i.e., in the order that the input is fed ...
3
votes
0
answers
163
views
Online bipartite edge-cover problem with requirements
I have $N$ nodes $v_1,\ldots,v_N$ in one partition $X$ and $M \leq N$ nodes $u_1,\ldots,u_M$ in a different partition $Y$. I want to connect nodes in $X$ to nodes in $Y$ with edges under the following ...
1
vote
0
answers
134
views
Competitive ratio of this paging algorithm
In the paging problem, we have a cache of size $k$ and a universe of $n>k$ pages.
In an online setting, we get requests for pages $p_1,p_2,\ldots p_t$, and are required to have page $p_i$ loaded ...
2
votes
1
answer
551
views
Methods for proving upper bound on a-approximiation algorithms? [closed]
I'm dealing with some simple randomized and on-line algorithms, both kind produce some lower/upper bound on quality of the output instance.
For example, there's a simple randomized algorithm for the ...
1
vote
1
answer
70
views
Search a preprocessed text with online queries
We're given a fixed text, and we are presented with a series of online queries of patterns. For each query, the goal is to answer if the pattern exists in the text. Each pattern is a string, and we ...
1
vote
0
answers
153
views
Winnow versus Perceptron - Why adding irrelevant features increases L2(X) but not L∞(X)?
I saw here: http://www.cs.cmu.edu/~ninamf/ML11/lect0906.pdf
Intuitively, if “n” is large but most features are irrelevant (i.e. target is sparse but examples are dense), then Winnow is better because ...
3
votes
1
answer
321
views
Can map-reduce speed up the count-min-sketch algorithm?
Is there any possibility of improvement in the result of count-min-sketch algorithm if we will use Map Reduce approach?
Improvement in performance can be in terms of accuracy, time complexity or the ...
5
votes
2
answers
375
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 * ...
1
vote
1
answer
1k
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. ...
2
votes
1
answer
473
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
1
answer
131
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 ...
5
votes
2
answers
1k
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
1
answer
63
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 flow ...
2
votes
0
answers
54
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 ...
5
votes
1
answer
827
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 data-...
3
votes
0
answers
643
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
0
answers
83
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
1
answer
314
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
1
answer
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
1
answer
137
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
2
answers
562
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
1
answer
888
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
2
answers
3k
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
0
answers
646
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 ...
17
votes
3
answers
4k
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
1
answer
72
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
2
answers
894
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 ...