The problem I have is the following: Given a sequence $x_1, \ldots, x_N$ for $N$ very large. For any $\varepsilon, \delta > 0$, find a number $\hat{x}_{\varepsilon, \delta}$ such that $$\mathbb{P}(e^{-\varepsilon}\max_i x_i \le \hat{x}_{\varepsilon, \delta} \le e^{\varepsilon}\max_ix_i) \ge 1 - \delta.$$ In words, the problem is to find an $\varepsilon$-approximate maximum of a sequence. There is a very rich literature on approximation algorithms and I am thinking the trivial (looking) problem of maximum of a sequence must have been studied.

(1) Are there algorithms known for this problem? The algorithms can only access each element of the sequence through the index. There is no space constraint but hopefully the time complexity is not N (for "good" sequences). If it helps, assume that the sequence consists of only a few distinct values, that is, $x_1, \ldots, x_N\in A$ for $|A| = s \ll N$.

(2) I understand that in the worst case the time complexity is N because the maximum can be anywhere. Are there existing time complexity bounds for this problem that depend on the sequence itself?

(3) If not constant factor approximation what is the best possible available?

Any references to the relevant literature would be appreciated. Thanks in advance.


Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.