ﻻ يوجد ملخص باللغة العربية
Several algorithms with an approximation guarantee of $O(log n)$ are known for the Set Cover problem, where $n$ is the number of elements. We study a generalization of the Set Cover problem, called the Partition Set Cover problem. Here, the elements are partitioned into $r$ emph{color classes}, and we are required to cover at least $k_t$ elements from each color class $mathcal{C}_t$, using the minimum number of sets. We give a randomized LP-rounding algorithm that is an $O(beta + log r)$ approximation for the Partition Set Cover problem. Here $beta$ denotes the approximation guarantee for a related Set Cover instance obtained by rounding the standard LP. As a corollary, we obtain improved approximation guarantees for various set systems for which $beta$ is known to be sublogarithmic in $n$. We also extend the LP rounding algorithm to obtain $O(log r)$ approximations for similar generalizations of the Facility Location type problems. Finally, we show that many of these results are essentially tight, by showing that it is NP-hard to obtain an $o(log r)$-approximation for any of these problems.
We consider the online Min-Sum Set Cover (MSSC), a natural and intriguing generalization of the classical list update problem. In Online MSSC, the algorithm maintains a permutation on $n$ elements based on subsets $S_1, S_2, ldots$ arriving online. T
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 comb
We investigate the polynomial-time approximability of the multistage version of Min-Sum Set Cover ($mathrm{DSSC}$), a natural and intriguing generalization of the classical List Update problem. In $mathrm{DSSC}$, we maintain a sequence of permutation
We study the classic set cover problem from the perspective of sub-linear algorithms. Given access to a collection of $m$ sets over $n$ elements in the query model, we show that sub-linear algorithms derived from existing techniques have almost tight
We carry out a systematic study of a natural covering problem, used for identification across several areas, in the realm of parameterized complexity. In the {sc Test Cover} problem we are given a set $[n]={1,...,n}$ of items together with a collecti