# Tagged Questions

The tag has no usage guidance.

86 views

137 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 ...
152 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 ...
281 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 ...
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 ...
404 views

622 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 ...
1k 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 ...
337 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 ...
2k 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 ...