Questions tagged [online-algorithms]
The online-algorithms tag has no usage guidance.
24
questions with no upvoted or accepted answers
8
votes
0
answers
365
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 ...
- 745
6
votes
1
answer
228
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
5
votes
0
answers
151
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 ...
- 901
5
votes
0
answers
222
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,073
5
votes
0
answers
180
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
3
votes
0
answers
51
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
3
votes
0
answers
120
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
2
votes
0
answers
67
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 ...
- 649
2
votes
0
answers
169
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
54
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
98
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
2
votes
0
answers
160
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,488
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
2
votes
0
answers
75
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
66
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
2
votes
0
answers
206
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
1
vote
0
answers
50
views
Streaming when doing computations with abstract term rewriting systems?
Computation models such as interaction nets can represent any computation as they are Turing complete.
However, I have been investigating their practical implementations, and I'm wondering if there's ...
- 11
1
vote
0
answers
43
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 ...
- 111
1
vote
0
answers
102
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,453
1
vote
0
answers
126
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
1
vote
0
answers
237
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
0
votes
0
answers
59
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
0
votes
0
answers
114
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,453
0
votes
1
answer
235
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