Source author record

Adi Rosen

Adi Rosen appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Data Structures and Algorithms

Catalog footprint

What is connected

2works

1topics

2close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2015arXiv

Space-Constrained Interval Selection

We study streaming algorithms for the interval selection problem: finding a maximum cardinality subset of disjoint intervals on the line. A deterministic 2-approximation streaming algorithm for this problem is developed, together with an algorithm for the special case of proper intervals, achieving improved approximation ratio of 3/2. We complement these upper bounds by proving that they are essentially best possible in the streaming setting: it is shown that an approximation ratio of $2 - ε$ (or $3 / 2 - ε$ for proper intervals) cannot be achieved unless the space is linear in the input size. In passing, we also answer an open question of Adler and Azar \cite{AdlerAzar03} regarding the space complexity of constant-competitive randomized preemptive online algorithms for the same problem.

preprint2014arXiv

Semi-Streaming Set Cover

This paper studies the set cover problem under the semi-streaming model. The underlying set system is formalized in terms of a hypergraph $G = (V, E)$ whose edges arrive one-by-one and the goal is to construct an edge cover $F \subseteq E$ with the objective of minimizing the cardinality (or cost in the weighted case) of $F$. We consider a parameterized relaxation of this problem, where given some $0 \leq ε< 1$, the goal is to construct an edge $(1 - ε)$-cover, namely, a subset of edges incident to all but an $ε$-fraction of the vertices (or their benefit in the weighted case). The key limitation imposed on the algorithm is that its space is limited to (poly)logarithmically many bits per vertex. Our main result is an asymptotically tight trade-off between $ε$ and the approximation ratio: We design a semi-streaming algorithm that on input graph $G$, constructs a succinct data structure $\mathcal{D}$ such that for every $0 \leq ε< 1$, an edge $(1 - ε)$-cover that approximates the optimal edge \mbox{($1$-)cover} within a factor of $f(ε, n)$ can be extracted from $\mathcal{D}$ (efficiently and with no additional space requirements), where \[ f(ε, n) = \left\{ \begin{array}{ll} O (1 / ε), & \text{if } ε> 1 / \sqrt{n} \\ O (\sqrt{n}), & \text{otherwise} \end{array} \right. \, . \] In particular for the traditional set cover problem we obtain an $O(\sqrt{n})$-approximation. This algorithm is proved to be best possible by establishing a family (parameterized by $ε$) of matching lower bounds.