The online-algorithms tag has no wiki summary.
0
votes
0answers
69 views
Early Stopping for Regularization, Explained
I'm trying to fully-comprehend the Wikipedia article on early stopping, as it pertains to regularizing a machine learning model.
On that page, it cites 6 steps to implement early stopping:
Divide ...
2
votes
0answers
41 views
Scheduling with RSVP deadline and possible cancellations
There is a sequence of events $e_1,\ldots,e_n$. $s(e_i), t(e_i)$ and $w(e_i)$ is the starting, terminating time and the weight of $e_i$, respectively. $p(e_i)$ is the probability of the event getting ...
13
votes
1answer
273 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 ...
8
votes
1answer
263 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 ...
6
votes
0answers
124 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 ...
7
votes
2answers
231 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 ...
3
votes
0answers
102 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
vote
0answers
68 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 ...
6
votes
2answers
137 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 ...
6
votes
0answers
190 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 ...
5
votes
2answers
739 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 ...
13
votes
2answers
250 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$
...
1
vote
1answer
163 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 ...
17
votes
2answers
445 views
maintaining a balanced spanning tree of a growing undirected graph
I am looking for ways to maintain a relatively balanced spanning tree of a graph, as I add new nodes/edges to the graph.
I have an undirected graph that starts as a single node, the "root".
At each ...
5
votes
1answer
555 views
What's the difference between online and incremental optimization?
Recently I've read some stuff about incremental optimization problems, but I can't see what's the difference between those and online optimization problems. My impression is that I can define every ...
12
votes
3answers
263 views
Is there a constant factor approximation algorithm for 2D rectangle coloring problem?
The problem we consider here is the extension of the well-known interval coloring problem. Instead of intervals we consider rectangles having sides parallel to axes. The objective is to color the ...
9
votes
3answers
549 views
Is there an online-algorithm to keep track of components in a changing undirected graph?
Problem
I have an undirected graph (with multi-edges), which will change over time, nodes and edges may be inserted and deleted. On each modification of the graph, I have to update the connected ...
13
votes
4answers
2k views
Algorithm for 'k'' most frequently occurring numbers
I have been searching for the most efficient (streaming??) algorithm that tells me the 'k' most frequently occurring elements in a data stream at any point in time. This post: ...
8
votes
4answers
298 views
Continuous Clustering
So I have an issue I'm facing in regards to clustering with live, continuously streaming data. Since I have an ever-growing data set I'm not sure what is the best way to run efficient and effective ...
