Skip to main content
OverflowAI is here! AI power for your Stack Overflow for Teams knowledge community. Learn more

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
0 answers
22 views

Randomized weighted majority with rational weights

Consider the RWM online algorithm as defined in this Wikipedia article; this version is with multiplicative update. Let us assume that we define our weights as a fraction; that is, $w_i^t = 1 / (M_i^t+...
Mahyar's user avatar
  • 81
1 vote
0 answers
18 views

Error correcting codes for stream of unkown size

Is there any algorithms like Reed Solomon that work for a stream of unknown data? The stream is finite but size is unknown until the stream ends. I found some information about sliding window reed-...
Miguel Ping's user avatar
0 votes
2 answers
71 views

Competitiveness of online algorithm

Is it possible for an online algorithm to perform better than the optimal solution for the offline version of a problem, and if so, in what circumstances? Doesn't competitive ratio rely on the fact ...
user592993's user avatar
0 votes
0 answers
55 views

How to find competitive ratio of any online algorithm?

I am starting to learn online algorithms but am still stuck in determining the competitive ratio. I cannot understand how to find it. All the research papers are so difficult to understand. Please ...
Michaylor Riya's user avatar
3 votes
2 answers
137 views

Sorted degrees and maximal degree in dynamic graphs

Consider a sequence of vertex and edge additions and removals to an initially empty (undirected, simple) graph. Is it possible to update the ordered list of vertex degrees in constant time (and space),...
Matthieu Latapy's user avatar
3 votes
0 answers
67 views

Algorithm for half-sample mode better than O(N^2)

The half-sample mode is a mode estimator that homes in on the highest density region of a set of samples in search of the mode. It is one of the better mode estimators, though it fails for J-shaped ...
Paul Chernoch's user avatar
1 vote
0 answers
36 views

External regret algorithms playing dominated strategies

Edit 3/14 to refer to textbook question: I am trying to understand the concept of external regret better, and am working through the Nisan et al. (eds.) Algorithmic Game Theory book (https://www.cs....
Andreas Haupt's user avatar
6 votes
1 answer
815 views

Fast and compact data structure for dynamic graphs

A graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$ may be represented in central memory as follows: an associative array (hash table) $V$ gives for any $v\in \mathcal{V}$ the list of its neighbors $V[v]$...
Matthieu Latapy's user avatar
0 votes
1 answer
72 views

Does this online problem have a specific name?

I came across the following family of online problems: Given a sequence of values of length n, the maximum value and the minimum value of the sequence, our goal: Given min and max, we want to find a ...
user206904's user avatar
2 votes
0 answers
33 views

Simple efficient algorithm for dynamically maintaining max of special linear functions

Given $n$ tuples $(k_i >0,a_i >0)$, is there any efficient algorithm that can dynamically track $$ \max_{i=1,\cdots,n} \left\{k_i\left(\sum_{j=1}^n a_j\right) - a_i\right\} $$ in response to ...
Chengyuan Ma's user avatar
1 vote
0 answers
72 views

Hardness result for online matching

Currently studying the following paper: "Fair Allocation in Online Markets" - Gollapudi and Panigrahi 2014 In which they present Theorem 2 as a hardness result for online maxmin matchings (...
user143196's user avatar
3 votes
0 answers
34 views

Online cycle detection but not quite: the Featherstitch problem

Featherstitch (Frost et al., 2007) is an approach for representing data consistency requirements for disk storage. This question concerns a graph-theoretic problem (§4.1 in the paper) that its ...
Alex Shpilkin's user avatar
2 votes
1 answer
81 views

Optimal online algorithm to guess the tree

I have a tree on $n$ vertices. Your goal is to find the adjacency list for it. $n$ is known to you from the start. You can pick a vertex and ask for the lengths of the shortests paths from it to the ...
mjb's user avatar
  • 21
1 vote
0 answers
27 views

Applications of derivative only, zeroth-order free optimization

I understand what is derivative-free optimization, and I am thinking a similar problem where the function $f$ we are optimizing is unknown and the only information we can acquire is the derivative. In ...
Francis's user avatar
  • 65
2 votes
0 answers
51 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 : ...
sten's user avatar
  • 139
1 vote
2 answers
396 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 ...
user133322's user avatar
0 votes
0 answers
88 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, ...
user avatar
1 vote
0 answers
78 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 ...
jae's user avatar
  • 11
0 votes
1 answer
86 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://...
aNormalPerson's user avatar
1 vote
1 answer
208 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 ...
zdm's user avatar
  • 1,046
2 votes
0 answers
64 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 ...
Shay's user avatar
  • 21
0 votes
0 answers
116 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 ...
zdm's user avatar
  • 1,046
0 votes
0 answers
23 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 ...
Fatemeh's user avatar
3 votes
1 answer
221 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 ...
Felix's user avatar
  • 161
0 votes
2 answers
146 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 ...
taktoa's user avatar
  • 364
2 votes
0 answers
32 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}}{...
Felix's user avatar
  • 161
1 vote
1 answer
214 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 ...
zdm's user avatar
  • 1,046
1 vote
0 answers
232 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 ...
kanso37's user avatar
  • 435
1 vote
0 answers
77 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 ...
Niels Uitterdijk's user avatar
3 votes
1 answer
237 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 ...
Avi Tal's user avatar
  • 339
1 vote
1 answer
56 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 ...
zdm's user avatar
  • 1,046
5 votes
3 answers
1k 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 ...
MJ13's user avatar
  • 177
1 vote
0 answers
47 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 ...
Niloy Saha's user avatar
2 votes
1 answer
401 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 ...
SomeoneHAHA's user avatar
1 vote
0 answers
25 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 ...
csTheoryBeginner's user avatar
1 vote
0 answers
80 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 ...
Niloy Saha's user avatar
0 votes
0 answers
24 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)}$...
Television's user avatar
2 votes
0 answers
298 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 ...
zdm's user avatar
  • 1,046
2 votes
1 answer
46 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 ...
Niloy Saha's user avatar
2 votes
0 answers
60 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 ...
Television's user avatar
2 votes
1 answer
287 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 ...
gradstudent's user avatar
1 vote
2 answers
76 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: ...
Niloy Saha's user avatar
0 votes
1 answer
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, ...
Niloy Saha's user avatar
2 votes
1 answer
486 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 ...
shaqed's user avatar
  • 361
1 vote
1 answer
342 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 ...
Mark Dominus's user avatar
  • 1,537
2 votes
0 answers
59 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 ...
Christian's user avatar
  • 121
1 vote
0 answers
45 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,...
neo4k's user avatar
  • 11
3 votes
1 answer
132 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 ...
nataman's user avatar
  • 53
3 votes
1 answer
94 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 ...
Evil's user avatar
  • 9,465
2 votes
1 answer
124 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....
SpiderRico's user avatar