Loading...
Loading...

Go to the content (press return)

An optimal anytime estimation algorithm

Author
Gavaldà, R.
Type of activity
Report
Date
2004-12
Code
LSI-04-56-R
Repository
http://hdl.handle.net/2117/87244 Open in new window
Abstract
In many applications a key step is estimating some unknown quantity ~$mu$ from a sequence of trials, each having expected value~$mu$. Optimal algorithms are known when the task is to estimate $mu$ within a multiplicative factor of $epsilon$, for an $epsilon$ given in advance. In this paper we consider {em anytime} approximation algorithms, i.e., algorithms that must give a reliable approximation after each trial, and whose approximations have to be increasingly accurate as the number of trials g...
Citation
Gavaldà, R. "An optimal anytime estimation algorithm". 2004.
Keywords
Approximation algorithms, Optimal algorithms
Group of research
LARCA - Laboratory of Relational Algorithmics, Complexity and Learnability

Participants

Attachments