Questions tagged [online-algorithms]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0 votes
0 answers
35 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 ...
George Moneftsis's user avatar
0 votes
1 answer
81 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 ...
Exulansis's user avatar
0 votes
0 answers
51 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 ...
white's user avatar
  • 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 ...
Amin's user avatar
  • 111
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 ...
Karagounis Z's user avatar
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 ...
Doc Stories's user avatar
2 votes
0 answers
164 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 ...
Matthieu Latapy's user avatar
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 ...
Timothy's user avatar
  • 121
2 votes
0 answers
95 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 ...
zdm's user avatar
  • 325
3 votes
0 answers
116 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 ...
Antimony's user avatar
  • 917
0 votes
0 answers
112 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 ...
gradstudent's user avatar
  • 1,453
1 vote
0 answers
100 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 ...
gradstudent's user avatar
  • 1,453
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 ...
zdm's user avatar
  • 325
1 vote
1 answer
143 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 ...
zdm's user avatar
  • 325
2 votes
1 answer
152 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 ...
zdm's user avatar
  • 325
2 votes
0 answers
149 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 ...
R B's user avatar
  • 9,448
1 vote
1 answer
262 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. ...
Gabriel Fair's user avatar
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 ...
PattaraS's user avatar
1 vote
1 answer
84 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 ...
kombinatorix's user avatar
2 votes
0 answers
74 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?
OmG's user avatar
  • 189
2 votes
0 answers
65 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 ...
rajatsen91's user avatar
4 votes
1 answer
166 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 ...
ivmihajlin's user avatar
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 ...
ivmihajlin's user avatar
0 votes
1 answer
284 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\...
user2789928's user avatar
6 votes
3 answers
986 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 ...
R B's user avatar
  • 9,448
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 ...
rabe's user avatar
  • 21
3 votes
1 answer
404 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 ...
user34725's user avatar
1 vote
0 answers
125 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 ...
user124384's user avatar
2 votes
1 answer
467 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 ...
Daniel's user avatar
  • 749
2 votes
2 answers
319 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-...
D.W.'s user avatar
  • 12.1k
8 votes
2 answers
512 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: ...
D.W.'s user avatar
  • 12.1k
1 vote
0 answers
236 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 ...
nomad's user avatar
  • 211
1 vote
1 answer
92 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 ...
David C's user avatar
  • 31
23 votes
1 answer
982 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 ...
a3nm's user avatar
  • 9,269
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 ...
George Tseres's user avatar
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 ...
Bach's user avatar
  • 133
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 ...
Mike Izbicki's user avatar
  • 1,073
6 votes
2 answers
381 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 ...
Geoffrey Irving's user avatar
0 votes
1 answer
407 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 ...
Jakub Kulhan's user avatar
14 votes
1 answer
481 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 ...
Arindam Pal's user avatar
  • 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,...
Arindam Pal's user avatar
  • 1,591
6 votes
1 answer
227 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 ...
nia's user avatar
  • 61
9 votes
3 answers
307 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$...
George's user avatar
  • 674
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 $...
Arindam Pal's user avatar
  • 1,591
-1 votes
1 answer
386 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 ...
Swair's user avatar
  • 107
6 votes
2 answers
192 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 ...
Goro Manpir's user avatar
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 ...
Elliot JJ's user avatar
  • 745
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 ...
Eliah's user avatar
  • 151
17 votes
2 answers
789 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,...
Justin Kilpatrick's user avatar
1 vote
1 answer
205 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 ...
J..y B..y's user avatar
  • 2,776