论文标题
动态套装：改进的摊销和最差的更新时间
Dynamic Set Cover: Improved Amortized and Worst-Case Update Time
论文作者
论文摘要
在动态最小设置盖问题中，一个挑战是最大程度地减少更新时间，同时确保接近最佳$ \ min（o（\ log n），f）$近似因子。 （整个过程，$ m $，$ n $，$ f $和$ c $都是参数，表示集合的最大数量，元素数量，频率和成本范围。）在高频范围内，当$ f =ω（\ log log n）$时，这是通过确定性$ o（\ log n）$ - log n）$ a $ ogpt a $ o（f imort a $ o（ al。 stoc'17]。在低频范围内，Gupta等人的工作线。 [Stoc'17]，Abboud等。 [Stoc'19]和Bhattacharya等。 [ICALP'15，IPCO'17，focs'19]带有$ O（f \ log（cn）/ε^2）$ amortized更新时间的确定性$（1+ε）F $ -Approximation算法。在本文中，我们改善了后一个更新时间，并提供了最先进的动态顶点覆盖算法（有时改善）的第一范围。我们获得： 1。$（1+ε）f $ - apptroximation比率$ o（f \ log^2（cn）/ε^3）$糟糕的更新时间：以前没有针对动态设置封面而闻名的非平凡的最差案例更新时间。我们的界限元素和对数因子的进步$ O（\ log^3 n/\ text {poly}（ε））$最差的更新时间是未加权的动态顶点封面（即，当$ f = 2 $和$ c = 1 $时，Bhattacharya et al ef bhattacharya等人。 [SODA'17]。 2。$（1+ε）f $ - approximation比率（（（（f^2/ε^3）+（f/ε^2） n）$。这是第一个独立于$ m $和$ n $的。它包含了Bhattacharya和Kulkarni [Soda'19]的持续摊销更新时间，以进行未加权的动态顶点盖（即，当$ f = 2 $和$ c = 1 $）。
In the dynamic minimum set cover problem, a challenge is to minimize the update time while guaranteeing close to the optimal $\min(O(\log n), f)$ approximation factor. (Throughout, $m$, $n$, $f$, and $C$ are parameters denoting the maximum number of sets, number of elements, frequency, and the cost range.) In the high-frequency range, when $f=Ω(\log n)$, this was achieved by a deterministic $O(\log n)$-approximation algorithm with $O(f \log n)$ amortized update time [Gupta et al. STOC'17]. In the low-frequency range, the line of work by Gupta et al. [STOC'17], Abboud et al. [STOC'19], and Bhattacharya et al. [ICALP'15, IPCO'17, FOCS'19] led to a deterministic $(1+ε)f$-approximation algorithm with $O(f \log (Cn)/ε^2)$ amortized update time. In this paper we improve the latter update time and provide the first bounds that subsume (and sometimes improve) the state-of-the-art dynamic vertex cover algorithms. We obtain: 1. $(1+ε)f$-approximation ratio in $O(f\log^2 (Cn)/ε^3)$ worst-case update time: No non-trivial worst-case update time was previously known for dynamic set cover. Our bound subsumes and improves by a logarithmic factor the $O(\log^3 n/\text{poly}(ε))$ worst-case update time for unweighted dynamic vertex cover (i.e., when $f=2$ and $C=1$) by Bhattacharya et al. [SODA'17]. 2. $(1+ε)f$-approximation ratio in $O\left((f^2/ε^3)+(f/ε^2) \log C\right)$ amortized update time: This result improves the previous $O(f \log (Cn)/ε^2)$ update time bound for most values of $f$ in the low-frequency range, i.e. whenever $f=o(\log n)$. It is the first that is independent of $m$ and $n$. It subsumes the constant amortized update time of Bhattacharya and Kulkarni [SODA'19] for unweighted dynamic vertex cover (i.e., when $f = 2$ and $C = 1$).
