The tag has no wiki summary.

learn more… | top users | synonyms

0
votes
0answers
70 views

Online complete-neighborhoods queries on simple and bipartite graphs

Let $G=(V,E)$ be a finite simple graph. On query $X\subseteq V$ s.t. $X$ is a clique of $G$, we would like to compute the complete-neighborhood $\Lambda(X):=\{v\in V \mid \forall x\in X .vx \in E \}$ ...
2
votes
2answers
59 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 ...
3
votes
0answers
172 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 ...
6
votes
2answers
172 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 ...
0
votes
1answer
109 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 ...
2
votes
0answers
49 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 ...
14
votes
1answer
303 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 ...
9
votes
1answer
398 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
1answer
174 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
241 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
110 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
79 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
148 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
230 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
841 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 ...
16
votes
2answers
303 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
171 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 ...
18
votes
2answers
514 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 ...
6
votes
1answer
808 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 ...
16
votes
3answers
294 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 ...
11
votes
3answers
812 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 ...
15
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
309 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 ...