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.

Filter by
Sorted by
Tagged with
0
votes
0answers
40 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 ...
1
vote
1answer
154 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 ...
2
votes
2answers
163 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 ...
1
vote
1answer
32 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 ...
2
votes
1answer
265 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 ...
0
votes
2answers
39 views

Online shortest path in ordered DAG

Suppose I have an edge-weighted connected rooted DAG $G = (V, E, r \in V, w \in E \to \mathbb{Z})$ where there exists a sequence of nonempty sets (called "levels") $L_0 = \{r\}, L_1 \subset ...
1
vote
0answers
15 views

Integrality gap in Online Problems and adaptation to competitive ratio

As we all know, in offline problems it is common practice to calculate the integrality gap to get some bound on the approximation ratio of the integral solution. Now this gap ($IG:=\frac{OPT_{frac}}{...
1
vote
0answers
27 views

Definitions of and difference between adaptive online adversary and adaptive offline adversary?

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 ...
1
vote
0answers
39 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 ...
0
votes
0answers
42 views

You're walking in a maze,you must visit all reachable squares of distance k. The performance of the algorithm is measured by the total distance walked

The maze is a 2D Grid of known width and height. it's composed of squares: a Wall or a room. You cannot walk into walls. from each room you can only get to adjacent rooms. ( you can't teleport) You ...
3
votes
1answer
223 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 ...
1
vote
1answer
43 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 ...
4
votes
3answers
258 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 ...
2
votes
4answers
5k 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 ...
1
vote
0answers
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 ...
2
votes
1answer
164 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 ...
1
vote
0answers
136 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 ...
1
vote
0answers
17 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 ...
1
vote
2answers
67 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: ...
1
vote
0answers
57 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 ...
0
votes
0answers
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)}$...
2
votes
1answer
38 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 ...
2
votes
0answers
36 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 ...
2
votes
1answer
183 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 ...
0
votes
1answer
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, ...
1
vote
1answer
170 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 ...
14
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 ...
2
votes
1answer
105 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....
2
votes
0answers
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 ...
1
vote
0answers
41 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,...
3
votes
1answer
87 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 ...
3
votes
1answer
76 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 ...
2
votes
1answer
180 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
2answers
121 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
0answers
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 ...
1
vote
0answers
93 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
1answer
379 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
1answer
63 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
0answers
142 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 ...
4
votes
2answers
653 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 ...
5
votes
2answers
354 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
1answer
330 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
984 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
1answer
1k 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
83 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
2answers
664 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
46 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
0answers
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 ...
11
votes
2answers
527 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 ...
1
vote
0answers
535 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 ...