14

دی

3

علاقه‌مند

زمان ثبت نام این رویداد به اتمام رسیده است . در صورتی که تا به حال ثبت نام نکرده‌اید به دفتر شاخه‌ مراجعه کنید.

On Streaming and Communication Complexity of the Set Cover Problem

On Streaming and Communication Complexity of the Set Cover Problem

We develop the first streaming algorithm and the first two-part communication protocol that uses a constant number of passes/rounds and sublinear space/communication for logarithmic approximation to the classic \prob{Set Cover} problem. Specifically, for $n$ elements and $m$ sets, our algorithm/protocol achieves a space bound of $O(m \cdot n^\delta \log^2 n \log m)$(for any $\delta > 0$) using $O(4^{1/\delta})$ passes/rounds while achieving an approximation factor of $O(4^{1/\delta} \log n)$ in polynomial time. If we allow the algorithm/protocol to spend exponential time per pass/round, we achieve an approximation factor of $O(4^{1/\delta})$.
Our approach uses randomization, which we show is necessary: no deterministic constant approximation is possible (even given exponential time) using $o(m n)$ space. These results are some of the first on streaming algorithms and efficient two-party communication protocols for approximation algorithms. Moreover, we show that our algorithm can be applied to multi-party communication model.
دوشنبه ۱۳ تا ۱۴ آمفی‌تئاتر دانشکده‌ی مهندسی برق و کامپیوتر

روز ساعت مدت