论文标题
带有小邻里物业的最小重量套盖的平行算法
A parallel algorithm for minimum weight set cover with small neighborhood property
论文作者
论文摘要
本文在\ cite {agarwal。}中研究了{\ em small邻里覆盖}（snc）属性的最小重量集覆盖率（MINWSC）问题。提出了带有$τ$ -SNC属性的Minwsc的平行算法，获得了近似值$τ（1+3 \ varepsilon）$ in $ o（l \ log_ {1+\ varepsilon} \ varepsilon} \ frac \ frac {n^3}回合，其中$ 0 <\ varepsilon <\ frac {1} {2} $是常数，$ n $是元素的数量，$ l $是与SNC属性相关的参数。我们的结果不仅提高了在\ cite {agarwal。}中获得的近似值，而且还回答了在\ cite {agarwal。}中提出的两个问题。
This paper studies the minimum weight set cover (MinWSC) problem with a {\em small neighborhood cover} (SNC) property proposed by Agarwal {\it et al.} in \cite{Agarwal.}. A parallel algorithm for MinWSC with $τ$-SNC property is presented, obtaining approximation ratio $τ(1+3\varepsilon)$ in $O(L\log_{1+\varepsilon}\frac{n^3}{\varepsilon^2}+ 4τ^{3}2^τL^2\log n)$ rounds, where $0< \varepsilon <\frac{1}{2}$ is a constant, $n$ is the number of elements, and $L$ is a parameter related to SNC property. Our results not only improve the approximation ratio obtained in \cite{Agarwal.}, but also answer two questions proposed in \cite{Agarwal.}.
