Questions tagged [online-algorithms]
Questions about algorithms that receive the input piecewise and have to make decisions, that is produce output, before having seen the whole input.
80 questions
2 votes
2 answers
267 views
Why does it make sense to minimize regret?
In fields such as game theory and reinforcement learning, it is standard to consider the regret-minimization strategy. I don't get the motivation for the definition. Yes, doing your best under worst-...
- 171
3 votes
3 answers
212 views
Detect if an interval is fully covered by union of previous intervals in sequence
Given a sequence of intervals $I_1, I_2, \ldots$, is there an efficient way to detect whether some interval $I_i$ is completely contained in the union of the preceding intervals $I_1, \ldots, I_{i-1}$?...
- 163
1 vote
0 answers
43 views
Error correcting codes for stream of unkown size
Is there any algorithms like Reed Solomon that work for a stream of unknown data? The stream is finite but size is unknown until the stream ends. I found some information about sliding window reed-...
- 121
0 votes
2 answers
102 views
Competitiveness of online algorithm
Is it possible for an online algorithm to perform better than the optimal solution for the offline version of a problem, and if so, in what circumstances? Doesn't competitive ratio rely on the fact ...
0 votes
0 answers
97 views
How to find competitive ratio of any online algorithm?
I am starting to learn online algorithms but am still stuck in determining the competitive ratio. I cannot understand how to find it. All the research papers are so difficult to understand. Please ...
3 votes
2 answers
222 views
Sorted degrees and maximal degree in dynamic graphs
Consider a sequence of vertex and edge additions and removals to an initially empty (undirected, simple) graph. Is it possible to update the ordered list of vertex degrees in constant time (and space),...
- 685
3 votes
0 answers
158 views
Algorithm for half-sample mode better than O(N^2)
The half-sample mode is a mode estimator that homes in on the highest density region of a set of samples in search of the mode. It is one of the better mode estimators, though it fails for J-shaped ...
- 261
1 vote
0 answers
57 views
External regret algorithms playing dominated strategies
Edit 3/14 to refer to textbook question: I am trying to understand the concept of external regret better, and am working through the Nisan et al. (eds.) Algorithmic Game Theory book (https://www.cs....
6 votes
1 answer
1k views
Fast and compact data structure for dynamic graphs
A graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$ may be represented in central memory as follows: an associative array (hash table) $V$ gives for any $v\in \mathcal{V}$ the list of its neighbors $V[v]$...
- 685
0 votes
1 answer
155 views
Does this online problem have a specific name?
I came across the following family of online problems: Given a sequence of values of length n, the maximum value and the minimum value of the sequence, our goal: Given min and max, we want to find a ...
- 320
2 votes
0 answers
59 views
Simple efficient algorithm for dynamically maintaining max of special linear functions
Given $n$ tuples $(k_i >0,a_i >0)$, is there any efficient algorithm that can dynamically track $$ \max_{i=1,\cdots,n} \left\{k_i\left(\sum_{j=1}^n a_j\right) - a_i\right\} $$ in response to ...
- 21
1 vote
0 answers
110 views
Hardness result for online matching
Currently studying the following paper: "Fair Allocation in Online Markets" - Gollapudi and Panigrahi 2014 In which they present Theorem 2 as a hardness result for online maxmin matchings (...
- 11
3 votes
0 answers
53 views
Online cycle detection but not quite: the Featherstitch problem
Featherstitch (Frost et al., 2007) is an approach for representing data consistency requirements for disk storage. This question concerns a graph-theoretic problem (§4.1 in the paper) that its ...
- 170
2 votes
1 answer
114 views
Optimal online algorithm to guess the tree
I have a tree on $n$ vertices. Your goal is to find the adjacency list for it. $n$ is known to you from the start. You can pick a vertex and ask for the lengths of the shortests paths from it to the ...
- 21
1 vote
0 answers
56 views
Applications of derivative only, zeroth-order free optimization
I understand what is derivative-free optimization, and I am thinking a similar problem where the function $f$ we are optimizing is unknown and the only information we can acquire is the derivative. In ...
- 75