# 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.

61 questions
Filter by
Sorted by
Tagged with
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 ...
684 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 ...
280 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 ...
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 ...
538 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 ...
125 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 ...
700 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 ...
354 views

38 views

### Hardness of approximation for online algorithms

Similar to the theory of hardness of approximation for (offline) approximation algorithms, has there been any work done on proving hardness guarantees for online algorithms? Theoretical lower bounds ...
291 views

### Competitive ratio of the ski rental problem

Reading about the Ski Rental Problem in Wikipedia, I got confused on the "when" is the buying of the skis occur. I could think of 2 possible ways, but each of them would have a different competitive ...
44 views

### What's the reason for sqrt(n) bounds in online learning?

I have a question regarding no-regret algorithms (of online learning). As far as I can see, such algorithms allow the absolute regret up to round $n$, which is $R_n$, to grow by $\sqrt{n}$. So, in the ...
44 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 ...
64 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 ...
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. ...
32 views

### How to prove that knapsack has no competitive algorithm

In online knapsack problem, items arrive one by one. Each time an item $i$ arrives, its weight $w_i$ is revealed. We would like to maximize, in an online fashion, the number of items placed in a bin ...
45 views

### Matching Upper Bound for Online Problems

I have an online problem and I want to prove that no deterministic online algorithm is competitive. Let $\texttt{ON}$ be an online algorithm and $\texttt{OPT}$ an optimal offline algorithm (an ...
68 views

### Online set filling with redistributions

Edited: Suppose we have 4 sets $A, B, C, D$ which can can hold a maximum of two elements, each. Now, elements ($E_i$) arrive serially with properties such as: ...
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. ...
48 views

### Solve the online unweighted 0-1 knapsack problem efficiently

I have $n$ items and a bin of size $B$ units. Each item $j$ consumes $w_j$ units of $B$ when placed into the knapsack. The item appears one-by-one in an online fashion. Once item $i$ appears, we must ...
178 views

### Is there an online algorithm for radix conversion?

Suppose I have $P$, which is the base-$p$ representation of an integer $n$ and I want to calculate it base-$q$ representation $Q$. The obvious algorithm is: interpret $P$ to obtain $n$, then ...
85 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 ...
46 views

I recently started learning about randomized online algorithms, and the Wikipedia definitions for the three adversary models are very unhelpful to put it mildly. From poking around I think I have a ...
45 views

### Proof of Fundamental Lower Bound on Regret

Online Convex Optimization sees optimization as a continuous process in which the algorithm learns new aspects of the problem and improves upon. Every iteration consists of the player making a ...
37 views

### Online Many-to-one Matching

Offline Problem I have a graph $\mathcal{G} = (\mathcal{D} \cup \mathcal{A}, \mathcal{E})$. Each edge $e \in \mathcal{E}$ between the two vertex sets $\mathcal{D}$ and $\mathcal{A}$ has an ...
18 views

### On the limitation of the “adversary” in randomization for online learning

While reading on randomization for online learning from the text "Online Learning and Online Convex Optimization" by Shai Shalev-Shwartz, I found the following statement (Pg 115)- "The adversary can ...
From Online Computation and Competitive Analysis By Allan Borodin, Ran El-Yaniv, to prove that an online algorithm $\text{ALG}$ is $c$-competitive for a minimization problem (i.e., there exists a ...