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

66 questions
Filter by
Sorted by
Tagged with
22 views

### Online algorithm for compressing multiple SETS?

Algorithms like LZW and others compress data sequences. What I'm looking is an algorithm that compress multiple Sets. if possible online algorithm. For example : ...
20 views

### Online approximation algorithm for median?

Is there a well-known or (relatively) easily-implementable streaming algorithm for approximating the median of the last, say, $k$ elements of a stream $c_1,c_2,c_3,\dots$? The scenario is: I have a ...
47 views

### Which of the following statement is true?

Given two statement: A:if inputs of a problem is online, then there is faster or equal algorithm in view of time complexity for that problem when input is offline. B:if inputs of a problem is offline, ...
44 views

### Experts problem with one perfect expert

This question concerns a variant of the 'experts' problem and the randomized weighted majority algorithm that can be used to solve it. This is the description of the problem from Wikipedia: Imagine ...
28 views

### How to simulate online matching algorithms (implementation)

I was reading about online algorithms and bipartite matching. I found an implementation that works fine on several websites (like geeksforgeeks). For the online version, I found this paper https://...
33 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 ...
30 views

### Is there an online preprocessing algorithm for Range Minimum Queries (RMQ)?

Is there a linear time online version of the preprocessing RMQ algorithm? That is, an algorithm that allows to update the data structure when appending additional elements at the end of the input ...
48 views

### What is an optimal online algorithm and how to design it to solve NP-hard problems?

To solve an NP-hard optimization problem optimally, we can use mathematical programming or brute force techniques. I would like to know if it is possible to solve the problem in an online fashion ...
14 views

### Does regret change when the loss function is dependent on the previous predictions?

The loss function of each expert in the expert advice problem(or any online learning problem) depends on the time($t$) and expert advice at that time($f_{t}(i)$). suppose in this problem, loss ...
45 views

### Scheduling jobs online on 3 identical machines - a lower bound of 5/3

Consider the Online Scheduling Problem with $3$ identical machines. Jobs, with arbitrary size arrive online one after another and need to be scheduled immediately on one of the $3$ machines without ...
191 views

### Weighted Online Matching - randomized algorithms

Let's consider the edge weighted online matching problem. The Vertices arrive online and reveal all their current edges and edge-weights $w_e>0$. The goal is to maximize the matchings weight. An ...
53 views

60 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 ...
61 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 ...
48 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 ...
225 views

### Matrix element value counting in O(1) space

The question arise from my customer's real-time system (RAM model, off-course), which has very limited resources. Given an NxM matrix of integer values, we need to verify that the number of non-zero ...
47 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 ...
363 views

### Finding the hidden treasure

Let's assume I am trying to find a hidden treasure. The treasure is hidden at an uknown position x. We know that the position x of the treasure is somewhere on the integer axis (in other words x is ...
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 ...
181 views

### Approximation algorithm for weighted set cover, using multiplicative weights

It is known that the problem of fractional set cover can be rephrased as a linear programming problem and be approximated using the multiplicative weights method, for instance this lecture note shows ...
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 ...
60 views

### Multi Arm Bandit (MAB) — Increasing reward function

In the general stochastic MAB model, the reward obtained at each trial is generally assumed to be independent of previous trials and obtained from some fixed (but unknown) distribution. However, if ...
14 views

### Optimizing convex function in an online manner

I have a convex function of $n$ variables, $f(x_1,x_2,\dots,x_n)$ and need to find its minimizer. Are there algorithms that can retrieve the minimizer in an online fashion? i.e. solve for $x_1^{(opt)}$...
171 views

### How to define the potential function method for an online maximization problem?

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 ...
39 views

### Online set cover variant? Routing of requests

We have a set of $k$ path requests from $src$ to $dst$ that arrive sequentially. Each request may have multiple paths, but can choose only one of them. For example, in the Figure shown, there are ...
40 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 ...
187 views

### Lower bounds on regret

In "regret" styled analysis over $T$ steps of an iterative algorithm $\{x_i \in F \}_{i=1}^T$ (where $F$ is some feasible set) being given the sequence of loss functions $\{ f_i\}_{i=1}^T$ one defines ...
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: ...
22 views

### Online Set Filling

Suppose we have 3 sets $A, B, C$ which can can hold a maximum of two elements, each. So the total number of elements that the sets can hold together i.e. total capacity (TC) is $3*2 = 6$. Now, ...
312 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 ...
188 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 ...
45 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 ...
42 views

### Update model parameter with new data, discarding old data

I have this dataset, and I am using y = (a * x^n) / (b + x^n) Hill function as the model, where a is the limit of the Hill curve,...
94 views

### Lower bound on competitive ratio of $m$-machine scheduling

Given a sequence of positive reals $a_1, a_2, \dots, a_n$ and an integer $m$, for each $j$ assign $a_j$ to a machine $i$, $1< i < m$, so as to minimize the maximum, over $i$, of the sum of all ...
78 views

### What is the best known data structure for online dk-NNG?

I want to build the distance constrained k-Nearest Neighbours Graph, i.e. for every point $p$ in the data cloud $P$ there are at most $k$ undirected edges to points that are closest among all possible ...
109 views

### Online algorithms and changing past decisions

We know that for some online problems, algorithms can decrease their competitive ratio greatly if they are allowed to change some of their past decisions (see http://epubs.siam.org/doi/pdf/10.1137/1....
217 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 ...
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 ...
6k 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 ...
158 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 ...
102 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 ...
405 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 ...
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 ...
147 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 ...
183 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 ...