Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA New Deterministic Algorithm for Dynamic Set Cover
101
0
0.0
(
0
)
Added by
Sayan Bhattacharya
Publication date
2019
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We present a deterministic dynamic algorithm for maintaining a $(1+epsilon)f$-approximate minimum cost set cover with $O(flog(Cn)/epsilon^2)$ amortized update time, when the input set system is undergoing element insertions and deletions. Here, $n$ denotes the number of elements, each element appears in at most $f$ sets, and the cost of each set lies in the range $[1/C, 1]$. Our result, together with that of Gupta et al. [STOC`17], implies that there is a deterministic algorithm for this problem with $O(flog(Cn))$ amortized update time and $O(min(log n, f))$-approximation ratio, which nearly matches the polynomial-time hardness of approximation for minimum set cover in the static setting. Our update time is only $O(log (Cn))$ away from a trivial lower bound. Prior to our work, the previous best approximation ratio guaranteed by deterministic algorithms was $O(f^2)$, which was due to Bhattacharya et al. [ICALP`15]. In contrast, the only result that guaranteed $O(f)$-approximation was obtained very recently by Abboud et al. [STOC`19], who designed a dynamic algorithm with $(1+epsilon)f$-approximation ratio and $O(f^2 log n/epsilon)$ amortized update time. Besides the extra $O(f)$ factor in the update time compared to our and Gupta et al.s results, the Abboud et al. algorithm is randomized, and works only when the adversary is oblivious and the sets are unweighted (each set has the same cost). We achieve our result via the primal-dual approach, by maintaining a fractional packing solution as a dual certificate. Unlike previous primal-dual algorithms that try to satisfy some local constraints for individual sets at all time, our algorithm basically waits until the dual solution changes significantly globally, and fixes the solution only where the fix is needed.
rate research
Read More
We design a Local Computation Algorithm (LCA) for the set cover problem. Given a set system where each set has size at most $s$ and each element is contained in at most $t$ sets, the algorithm reports whether a given set is in some fixed set cover whose expected size is $O(log{s})$ times the minimum fractional set cover value. Our algorithm requires $s^{O(log{s})} t^{O(log{s} cdot (log log{s} + log log{t}))}$ queries. This result improves upon the application of the reduction of [Parnas and Ron, TCS07] on the result of [Kuhn et al., SODA06], which leads to a query complexity of $(st)^{O(log{s} cdot log{t})}$. To obtain this result, we design a parallel set cover algorithm that admits an efficient simulation in the LCA model by using a sparsification technique introduced in [Ghaffari and Uitto, SODA19] for the maximal independent set problem. The parallel algorithm adds a random subset of the sets to the solution in a style similar to the PRAM algorithm of [Berger et al., FOCS89]. However, our algorithm differs in the way that it never revokes its decisions, which results in a fewer number of adaptive rounds. This requires a novel approximation analysis which might be of independent interest.
We present a packing-based approximation algorithm for the $k$-Set Cover problem. We introduce a new local search-based $k$-set packing heuristic, and call it Restricted $k$-Set Packing. We analyze its tight approximation ratio via a complicated combinatorial argument. Equipped with the Restricted $k$-Set Packing algorithm, our $k$-Set Cover algorithm is composed of the $k$-Set Packing heuristic cite{schrijver} for $kgeq 7$, Restricted $k$-Set Packing for $k=6,5,4$ and the semi-local $(2,1)$-improvement cite{furer} for 3-Set Cover. We show that our algorithm obtains a tight approximation ratio of $H_k-0.6402+Theta(frac{1}{k})$, where $H_k$ is the $k$-th harmonic number. For small $k$, our results are 1.8667 for $k=6$, 1.7333 for $k=5$ and 1.5208 for $k=4$. Our algorithm improves the currently best approximation ratio for the $k$-Set Cover problem of any $kgeq 4$.
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=Omega(log n)$, this was achieved by a deterministic $O(log n)$-approximation algorithm with $O(f log n)$ amortized update time [Gupta et al. STOC17]. In the low-frequency range, the line of work by Gupta et al. [STOC17], Abboud et al. [STOC19], and Bhattacharya et al. [ICALP15, IPCO17, FOCS19] led to a deterministic $(1+epsilon)f$-approximation algorithm with $O(f log (Cn)/epsilon^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+epsilon)f$-approximation ratio in $O(flog^2 (Cn)/epsilon^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}(epsilon))$ worst-case update time for unweighted dynamic vertex cover (i.e., when $f=2$ and $C=1$) by Bhattacharya et al. [SODA17]. 2. $(1+epsilon)f$-approximation ratio in $Oleft((f^2/epsilon^3)+(f/epsilon^2) log Cright)$ amortized update time: This result improves the previous $O(f log (Cn)/epsilon^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 [SODA19] for unweighted dynamic vertex cover (i.e., when $f = 2$ and $C = 1$).
This study considers the (soft) capacitated vertex cover problem in a dynamic setting. This problem generalizes the dynamic model of the vertex cover problem, which has been intensively studied in recent years. Given a dynamically changing vertex-weighted graph $G=(V,E)$, which allows edge insertions and edge deletions, the goal is to design a data structure that maintains an approximate minimum vertex cover while satisfying the capacity constraint of each vertex. That is, when picking a copy of a vertex $v$ in the cover, the number of $v$s incident edges covered by the copy is up to a given capacity of $v$. We extend Bhattacharya et al.s work [SODA15 and ICALP15] to obtain a deterministic primal-dual algorithm for maintaining a constant-factor approximate minimum capacitated vertex cover with $O(log n / epsilon)$ amortized update time, where $n$ is the number of vertices in the graph. The algorithm can be extended to (1) a more general model in which each edge is associated with a nonuniform and unsplittable demand, and (2) the more general capacitated set cover problem.
In a minimum cost submodular cover problem (MinSMC), given a monotone non-decreasing submodular function $fcolon 2^V rightarrow mathbb{Z}^+$, a cost function $c: Vrightarrow mathbb R^{+}$, an integer $kleq f(V)$, the goal is to find a subset $Asubseteq V$ with the minimum cost such that $f(A)geq k$. MinSMC has a lot of applications in machine learning and data mining. In this paper, we design a parallel algorithm for MinSMC which obtains a solution with approximation ratio at most $frac{H(min{Delta,k})}{1-5varepsilon}$ with probability $1-3varepsilon$ in $O(frac{log mlog nlog^2 mn}{varepsilon^4})$ rounds, where $Delta=max_{vin V}f(v)$, $H(cdot)$ is the Hamornic number, $n=f(V)$, $m=|V|$ and $varepsilon$ is a constant in $(0,frac{1}{5})$. This is the first paper obtaining a parallel algorithm for the weighted version of the MinSMC problem with an approximation ratio arbitrarily close to $H(min{Delta,k})$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
