We present a $(1+\frac{k}{k+2})$-approximation algorithm for the Maximum $k$-dependent Set problem on bipartite graphs for any $k\ge1$. For a graph with $n$ vertices and $m$ edges, the algorithm runs in $O(k m \sqrt{n})$ time and improves upon the previously best-known approximation ratio of $1+\frac{k}{k+1}$ established by Kumar et al. [Theoretical Computer Science, 526: 90--96 (2014)]. Our proof also indicates that the algorithm retains its approximation ratio when applied to the (more general) class of K\"{o}nig-Egerv\'{a}ry graphs.
翻译：我们为任何KK\Ge1$的双方图中的最大 $k$依赖的Set 问题提出了一个$( 1 {k{k}k+2}) 的 $- 接近算法。 对于一个有 $n\ ge$ 和 $m 边缘的图表, 算法以$( km\ sqrt{n}) 时间运行, 并改进了 Kumar et al. [理论计算机科学, 526: 90- 96 (2014)] 建立的最著名的 $frac{k}+1美元近似比 。 我们的证据还表明, 当应用 K\\\ { o} nig- Egerv\ { a} ry 图时, 该算法保持其近似比率 。
相关内容
微信扫码咨询专知VIP会员