A streaming algorithm for 2-center with outliers in high dimensions

详细信息    查看全文

• 作者：Behnam Hatami ^{bhatami@ce.sharif.edu" class="auth_mail" title="E-mail the corresponding author} ; Hamid Zarrabi-Zadeh ; ^{zarrabi@sharif.edu" class="auth_mail" title="E-mail the corresponding author}
• 关键词：k-Center ; Outlier ; High dimensions ; Data stream
• 刊名：Computational Geometry
• 出版年：2017
• 出版时间：January 2017
• 年：2017
• 卷：60
• 期：Complete
• 页码：26-36
• 全文大小：379 K

文摘

We study the 2-center problem with outliers in high-dimensional data streams. Given a stream of points in arbitrary d dimensions, the goal is to find two congruent balls of minimum radius covering all but at most z   points. We present a class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0925772116300645&_mathId=si1.gif&_user=111111111&_pii=S0925772116300645&_rdoc=1&_issn=09257721&md5=1d24fc31c805f50796f266d14798f93d" title="Click to view the MathML source">(1.8+ε)class="mathContainer hidden">class="mathCode">$(1.8+\epsilon )$-approximation streaming algorithm, improving over the previous class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0925772116300645&_mathId=si2.gif&_user=111111111&_pii=S0925772116300645&_rdoc=1&_issn=09257721&md5=ee599769af1c75fc91347426530a7549" title="Click to view the MathML source">(4+ε)class="mathContainer hidden">class="mathCode">$(4+\epsilon )$-approximation algorithm available for the problem. The space complexity and update time of our algorithm are class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0925772116300645&_mathId=si3.gif&_user=111111111&_pii=S0925772116300645&_rdoc=1&_issn=09257721&md5=92a4afc8716a28b9053369d4d827b08f" title="Click to view the MathML source">poly(d,z,1/ε)class="mathContainer hidden">class="mathCode">$\mathrm{poly}(d,z,1/\epsilon )$, independent of the size of the stream.