Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > DATA STREAMING:
Reports tagged with data streaming:
TR07-088 | 7th September 2007

#### Adaptive Algorithms for Online Decision Problems

Revisions: 1

We study the notion of learning in an oblivious changing environment. Existing online learning algorithms which minimize regret are shown to converge to the average of all locally optimal solutions. We propose a new performance metric, strengthening the standard metric of regret, to capture convergence to locally optimal solutions, and ... more >>>

TR15-113 | 9th July 2015
Amit Chakrabarti, Tony Wirth

#### Incidence Geometries and the Pass Complexity of Semi-Streaming Set Cover

Set cover, over a universe of size $n$, may be modelled as a
data-streaming problem, where the $m$ sets that comprise the instance
are to be read one by one. A semi-streaming algorithm is allowed only
$O(n \text{ poly}\{\log n, \log m\})$ space to process this ... more >>>

ISSN 1433-8092 | Imprint