Questions tagged [online-algorithms]
The online-algorithms tag has no usage guidance.
56
questions
0
votes
0
answers
33
views
Using an offline approximation algorithm within an online algorithm
When defining an online algorithm, it is common to assume that there exists an optimal offline algorithm to be used over the set of already known requests.
For example, consider the IGNORE algorithm ...
0
votes
1
answer
53
views
Generalized assignment problem with overall budget
The problem has N tasks. We have M workers. We have the cost of assigning task i to worker j. We have a profit for assigning task i to worker j. We want to assign each task to exactly one worker. One ...
0
votes
0
answers
47
views
The complexity order of regret (especially in online reinforcement learning)?
In online reinforcement learning theory, how to judge the complexity order of regret, if there are two or more terms in there?
For example, the state space is $X$, the action space is $A$, the episode ...
- 1
1
vote
0
answers
42
views
What is the meaning of loss in online convex optimization?
I am studying online convex optimization, and it is stated that when we make a decision, we observe loss corresponding to our decision. In some problems like multi-armed bandit problems, we know the ...
- 61
2
votes
0
answers
66
views
Confusion with the definition of Online Set Cover
I am confused on a technicality on how Online Set Cover is defined.
One way to define it is: We are given a collection of sets $\mathcal{S}$ upfront, and in each time-step an element arrives to be ...
- 607
3
votes
0
answers
49
views
Online assignment lower bound results
I am reading the following paper which presents a $(1-\epsilon)$-competitive online algorithm for the MaxMin (similar to the makespan) problem, defined as follows:
a set of requests are arriving in an ...
- 31
2
votes
0
answers
146
views
On-line pagerank in a streaming DAG (Directed Acyclic Graph)
Assume a DAG (Directed Acyclic Graph) is given as a stream of edges such that edge $(u,v)$ is given only after all incoming edges of $u$ are given. Let us denote by $n$ and $m$ the number of vertices ...
- 693
2
votes
0
answers
52
views
Dynamic permutation cycle data
Let $\pi \in S_n$ be a permutation of $\{1, \ldots, n\}$. Does there exist a simple data structure that admits the following operations in polylogarithmic time?
sameCycle($\pi,x,y$): determines ...
- 121
2
votes
0
answers
94
views
Is there a competitive algorithm for this online scheduling problem to minimize the truncated gaps?
Time is discrete. There are $n$ time-slots and a single job that can be scheduled on one machine of budget $B$. If the job is scheduled at time-slot $t$, then it will consume $c(t)$ units of the ...
- 325
3
votes
0
answers
105
views
Incremental PDA emptiness testing?
Is there anything known about the problem of incremental emptiness testing for a pushdown automata?
Suppose you have a PDA with (up to) $n$ states and transitions, but instead of being given the ...
- 917
0
votes
0
answers
103
views
Using martingale arguments to prove convergence of iterative algorithms
Can someone give me typical/educative examples of how martingales can be used to prove convergence of an iterative algorithmS?
The examples I know of can only go so far as to show that there exists ...
- 1,443
1
vote
0
answers
99
views
What is the state of the art in first order stochastic convex optimization?
What is the optimally fastest convex risk minimizing algorithm which only uses a stochastic first order oracle? Is this SGD?
What is the optimally fastest convex function minimizing algorithm which ...
- 1,443
0
votes
1
answer
225
views
A Simple Auction Game
You are playing the following game.
You have a budget of $B$ dollars. There are $n$ days. Every day $d$, you have to make a bid $b_d\geq0$ that does not exceed your budget. After making the bid, a ...
- 325
1
vote
1
answer
142
views
How to design an online algorithm for secretary problem with multiple players?
We have $k$ bins of capacity $c_i$ each. These bins appear in an online fashion, say on day $i$, bin $i$ appears. There are $l$ balls. Ball $j$ has weight $w_{ij}$ with bin $i$.
Each ball knows that ...
- 325
2
votes
1
answer
151
views
Solving an online problem without maximizing or minimizing an objective
You have a budget $B$ and a satisfaction level $L$. An indivisible product is available for sell and you are interested in buying. The product is divided into $n$ parts. Part $i$ of the product has ...
- 325
2
votes
0
answers
140
views
What is the competitive ratio of a $d$-way associative LRU cache?
In a caching problem, items arrive online, and the algorithm needs to decide which elements to keep in the cache. If the current item is not cached, we pay a penalty of $1$.
It is well known that for ...
- 9,428
1
vote
1
answer
256
views
Does every online algorithm has an offline counterpart?
According to the wikipedia page for Online algorithms, it states:
"Not every online algorithm has an offline counterpart."
At the time of asking this question there is no citation for this claim.
...
- 129
2
votes
0
answers
90
views
Is there any online problem that the best known competitive ratio is better than the hardness of approximation (or the best known approximation)?
In online-setting, we usually allow exponential time to think and come up with a strategy. On the other hand, in offline-setting, we might care about solving a particular problem optimally, or as good ...
- 21
1
vote
1
answer
83
views
Searching for the original definition of online algorithms
I'm currently searching for the original formal definition of online algorithms. The earliest mentions of online algorithms that I found are from the mid 80s. But none of these papers seem to be the ...
- 31
2
votes
0
answers
70
views
Efficient Online Algorithms for Matrix rank
Suppose, we have a matrix with known rank. Then, in each step one element of this matrix will be changed. Is there any efficient online algorithm to find rank of each matrix after each element update?
- 189
2
votes
0
answers
63
views
Problem dependent lower bound for stochastic bandits with full information
Suppose you have a $K$ armed stochastic bandit problem but with full information. There are $K$ arms with mean rewards $\mu_1,...,\mu_K$. At each step we have to select an arm, collect the reward from ...
- 245
4
votes
1
answer
165
views
Algorithms in preprocessed universe [closed]
In celebrated paper Clustered integer 3SUM via additive combinatorics by TM Chan and M Lewenstein one of the provided algorithms is the one for preprocessed universe. They were able to provide an ...
- 849
5
votes
0
answers
150
views
Online triangle counting
Please consider the following problem. It can (but probably shouldn't) be called offline version of online triangle detection on subgraphs.
Given a graph $G$ and a collection $C$ of subsets of ...
- 849
0
votes
1
answer
278
views
Online/approximate weighted and capacitated bipartite matching
I wish to take a look at online/approximate weighted and capacitated bipartite matching problem.
Consider $G=\{L\cup R, E\}$, $|L|=n_1$, $|R|=n_2$, $|E|=m$ and $E\subseteq L\times R$. For each $r_i\...
- 119
6
votes
3
answers
961
views
Algorithm for finding heavy hitters in a weighted stream
The problem of finding heavy hitters in a stream is defined as follows: given a $N$ sized stream of elements, return a set $\mathcal D$, such that every item which arrived at least $N\theta$ times ...
- 9,428
2
votes
0
answers
205
views
Convergence of online convex optimization methods
I am new to this subject so this question might seem a bit trivial
Assume that in each round $t\in{{1,...T}}$ we choose $x_t\in K $ where $K$ is a compact and convex set, The common methods for ...
- 21
3
votes
1
answer
400
views
Lookup complexity in augmented interval tree
If we consider the following problem:
Stream of intervals, coming in one at a time, which we maintain in an augmented interval tree (Interval tree). At some point in time later, we get a point,
and ...
- 39
1
vote
0
answers
118
views
Minimum size counter-example in a 2-machine scheduling problem proof
I'm confused about something in the main proof in this paper (sorry that it's behind a paywall, but I assume many people on here have access to such things through their university and my posting the ...
- 111
2
votes
1
answer
463
views
Follow the Perturbed Leader for nonlinear cost functions
The famous FTPL algorithm [1] is analyzing linear cost function. Is there any generalized proof for nonlinear functions known?
Note that in the last paragraph of [1] it says "It would be great to ...
- 749
2
votes
2
answers
309
views
Sketches, using ideal hash functions
I've been reading about sketches for processing streaming data (the CountMin sketch, the Count sketch, the tug-of-war sketch, FM sketches, etc.). They use hash functions that are required to be 2-...
- 11.6k
8
votes
2
answers
507
views
Streaming algorithms suitable for undergrad course
I am looking for interesting streaming algorithms that would be suitable for presentation in an undergraduate algorithms course.
Good choices should probably satisfy the following requirements:
...
- 11.6k
1
vote
0
answers
235
views
Automatically Adapting Forgetting Factor for Online EM
I've been reading some interesting papers recently on methods for automatically and adaptively setting the learning rate in stochastic gradient descent (SGD). In particular, "No more pesky learning ...
- 211
1
vote
1
answer
89
views
Are there published algorithms for on-line creation of AVL trees from ordered streams?
Given an ordered stream of n items (n unknown in advance), it is well-known how to construct a red-black tree from them in O(n)-time. More specifically this is possible using only O(log n) additional ...
- 31
23
votes
1
answer
950
views
Languages recognized by polynomial-size DFAs
For a fixed finite alphabet $\Sigma$, a formal language $L$ over $\Sigma$ is regular if there exists a deterministic finite automaton (DFA) over $\Sigma$ which accepts exactly $L$.
I am interested in ...
- 8,856
3
votes
1
answer
238
views
Definition of fractional in theoretical CS
What is the definition of the word "fractional" in algorithms? I have encountered the word in phrases like "fractional algorithm", "fractional node routing problem".
Note: English is not my native ...
- 133
2
votes
2
answers
79
views
Fast algorithm for linear context finding
I am trying to figure out a quick algorithm which solves the following problem.
For the rest of this question, assume $0\in\mathbb{N}$.
Denote by $\mathbb{R}^\mathbb{N}$ the set of all real ...
- 133
5
votes
0
answers
220
views
Is there an online algorithm for solving any P-complete problem?
We can think of the class $NC$ as the class of problems that can be solved in parallel, whereas a $P$-complete problem probably has no parallel solution. My question is: where do online algorithms ...
- 1,063
6
votes
2
answers
377
views
Maintaining the product of a queue of semigroup elements
I have a queue $Q$ where elements can be popped from the left and added to the right in $O(1)$ time. The elements are members of a fixed semigroup $S$ with $O(1)$ time multiplication. Let the ...
- 3,243
0
votes
1
answer
406
views
Capacity planning algorithm resources
Let's say I have a machine with many boxes of different sizes. I want to put packages inside those boxes. Packages arrive at different time and then stay in the box for specific period of time. I need ...
- 101
14
votes
1
answer
476
views
Is it enough for linear program constraints to be satisfied in expectation?
In the paper Randomized Primal-Dual analysis of RANKING for Online Bipartite Matching, while proving that the RANKING algorithm is $\left(1 - \frac{1}{e}\right)$-competitive, the authors show that the ...
- 1,591
13
votes
2
answers
1k
views
Online Algorithms books
Are there any recent books on Online Algorithms? I know of only two books on the subject.
Online Computation and Competitive Analysis by Allan Borodin and Ran El-Yaniv: This is a classic but old book,...
- 1,591
6
votes
1
answer
223
views
What are good set size estimation algorithms for small sets (around 10-50 elements)?
I'm trying to implement an online distinct counting algorithm, and I have thousands of small sets of 32 bit IP addresses whose sizes I want to estimate with high accuracy (1-5%).
I came across quite ...
- 61
8
votes
2
answers
266
views
Cheap online selection with weighted comparisons
Suppose we want to find the smallest element of a set $S$, whose elements are indexed from $1$ to $n$. We do not have access to the values of these elements, but we can compare any two elements of $S$...
- 664
5
votes
0
answers
177
views
Online Interval Coloring Problem
We are given a path $P = (V,E)$ on $n$ nodes, where each edge $e \in E$ has a capacity $c_e$. There are a set of $k$ requests $R_1,\ldots,R_k$. Request $R_i$ has a demand $d_i$, and has an interval $...
- 1,591
-1
votes
1
answer
368
views
Competitive ratio of Move To Front in alternate access - List Update Problem
I need to prove that the modification of MTF, Move to front on every even request of an element, list update problem has a competitive ratio of 2.
How does one go about proving such results? (I'm ...
- 107
6
votes
2
answers
189
views
Can a non-competitive deterministic algorithm be k-competitive if randomized?
Let's say there is a problem in which all possible deterministic online algorithms tha solve this problem are not-competitive.
Does this mean that a randomized online algorithm for the same problem ...
- 61
8
votes
0
answers
359
views
View of Multiplicative Weights in contexts of combinatorial optimization, low-regret/online optimization, and entropy-regularized gradient descent?
Also called exponentiated gradient.
I understand these are three places where multiplicative weights shows up (i.e. $w_{t+1} = w_{t}e^{- \text{loss}(w_{t})}$ or variations. And I understand a bit ...
- 735
5
votes
2
answers
1k
views
Brackets expression incremental parsing algorithm
I am looking for efficient and easy in implementation algorithm for incremental parsing of expressions with brackets.
Consider the example with expression like "((1)())(2)". Parse tree for that ...
- 151
17
votes
2
answers
783
views
Does an algorithm exist to efficiently maintain connectedness information for a DAG in presence of inserts/deletes?
Given a directed acyclic graph, $G(V,E)$, is it possible to efficiently support the following operations?
$isConnected(G,a,b)$: Determines if there is a path in $G$ from node $a$ to node $b$
$link(G,...
1
vote
1
answer
204
views
Has this online problem been studied before ?
Consider the following online problem:
For $\sigma$ and $k$ fixed, given a string of symbols from alphabet
$[1..\sigma]$, given one by one, guess a set $S$ of $k$ symbols such that the
next ...
- 2,733