Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn the Approximability of Multistage Min-Sum Set Cover
70
0
0.0
(
0
)
Added by
Vasileios Nakos
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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 permutations $(pi^0, pi^1, ldots, pi^T)$ on $n$ elements, based on a sequence of requests $(R^1, ldots, R^T)$. We aim to minimize the total cost of updating $pi^{t-1}$ to $pi^{t}$, quantified by the Kendall tau distance $mathrm{D}_{mathrm{KT}}(pi^{t-1}, pi^t)$, plus the total cost of covering each request $R^t$ with the current permutation $pi^t$, quantified by the position of the first element of $R^t$ in $pi^t$. Using a reduction from Set Cover, we show that $mathrm{DSSC}$ does not admit an $O(1)$-approximation, unless $mathrm{P} = mathrm{NP}$, and that any $o(log n)$ (resp. $o(r)$) approximation to $mathrm{DSSC}$ implies a sublogarithmic (resp. $o(r)$) approximation to Set Cover (resp. where each element appears at most $r$ times). Our main technical contribution is to show that $mathrm{DSSC}$ can be approximated in polynomial-time within a factor of $O(log^2 n)$ in general instances, by randomized rounding, and within a factor of $O(r^2)$, if all requests have cardinality at most $r$, by deterministic rounding.
rate research
Read More
We study the generalized min sum set cover (GMSSC) problem, wherein given a collection of hyperedges $E$ with arbitrary covering requirements $k_e$, the goal is to find an ordering of the vertices to minimize the total cover time of the hyperedges; a hyperedge $e$ is considered covered by the first time when $k_e$ many of its vertices appear in the ordering. We give a $4.642$ approximation algorithm for GMSSC, coming close to the best possible bound of $4$, already for the classical special case (with all $k_e=1$) of min sum set cover (MSSC) studied by Feige, Lov{a}sz and Tetali, and improving upon the previous best known bound of $12.4$ due to Im, Sviridenko and van der Zwaan. Our algorithm is based on transforming the LP solution by a suitable kernel and applying randomized rounding. This also gives an LP-based $4$ approximation for MSSC. As part of the analysis of our algorithm, we also derive an inequality on the lower tail of a sum of independent Bernoulli random variables, which might be of independent interest and broader utility. Another well-known special case is the min sum vertex cover (MSVC) problem, in which the input hypergraph is a graph and $k_e = 1$, for every edge. We give a $16/9$ approximation for MSVC, and show a matching integrality gap for the natural LP relaxation. This improves upon the previous best $1.999946$ approximation of Barenholz, Feige and Peleg. (The claimed $1.79$ approximation result of Iwata, Tetali and Tripathi for the MSVC turned out have an unfortunate, seemingly unfixable, mistake in it.) Finally, we revisit MSSC and consider the $ell_p$ norm of cover-time of the hyperedges. Using a dual fitting argument, we show that the natural greedy algorithm achieves tight, up to NP-hardness, approximation guarantees of $(p+1)^{1+1/p}$, for all $pge 1$. For $p=1$, this gives yet another proof of the $4$ approximation for MSSC.
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. The algorithm serves each set $S_t$ upon arrival, using its current permutation $pi_{t}$, incurring an access cost equal to the position of the first element of $S_t$ in $pi_{t}$. Then, the algorithm may update its permutation to $pi_{t+1}$, incurring a moving cost equal to the Kendall tau distance of $pi_{t}$ to $pi_{t+1}$. The objective is to minimize the total access and moving cost for serving the entire sequence. We consider the $r$-uniform version, where each $S_t$ has cardinality $r$. List update is the special case where $r = 1$. We obtain tight bounds on the competitive ratio of deterministic online algorithms for MSSC against a static adversary, that serves the entire sequence by a single permutation. First, we show a lower bound of $(r+1)(1-frac{r}{n+1})$ on the competitive ratio. Then, we consider several natural generalizations of successful list update algorithms and show that they fail to achieve any interesting competitive guarantee. On the positive side, we obtain a $O(r)$-competitive deterministic algorithm using ideas from online learning and the multiplicative weight updates (MWU) algorithm. Furthermore, we consider efficient algorithms. We propose a memoryless online algorithm, called Move-All-Equally, which is inspired by the Double Coverage algorithm for the $k$-server problem. We show that its competitive ratio is $Omega(r^2)$ and $2^{O(sqrt{log n cdot log r})}$, and conjecture that it is $f(r)$-competitive. We also compare Move-All-Equally against the dynamic optimal solution and obtain (almost) tight bounds by showing that it is $Omega(r sqrt{n})$ and $O(r^{3/2} sqrt{n})$-competitive.
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.
Optimization problems consist of either maximizing or minimizing an objective function. Instead of looking for a maximum solution (resp. minimum solution), one can find a minimum maximal solution (resp. maximum minimal solution). Such flipping of the objective function was done for many classical optimization problems. For example, Minimum Vertex Cover becomes Maximum Minimal Vertex Cover, Maximum Independent Set becomes Minimum Maximal Independent Set and so on. In this paper, we propose to study the weighted version of Maximum Minimal Edge Cover called Upper Edge Cover, a problem having application in the genomic sequence alignment. It is well-known that Minimum Edge Cover is polynomial-time solvable and the flipped version is NP-hard, but constant approximable. We show that the weighted Upper Edge Cover is much more difficult than Upper Edge Cover because it is not $O(frac{1}{n^{1/2-varepsilon}})$ approximable, nor $O(frac{1}{Delta^{1-varepsilon}})$ in edge-weighted graphs of size $n$ and maximum degree $Delta$ respectively. Indeed, we give some hardness of approximation results for some special restricted graph classes such as bipartite graphs, split graphs and $k$-trees. We counter-balance these negative results by giving some positive approximation results in specific graph classes.
In the problem of minimum connected dominating set with routing cost constraint, we are given a graph $G=(V,E)$, and the goal is to find the smallest connected dominating set $D$ of $G$ such that, for any two non-adjacent vertices $u$ and $v$ in $G$, the number of internal nodes on the shortest path between $u$ and $v$ in the subgraph of $G$ induced by $D cup {u,v}$ is at most $alpha$ times that in $G$. For general graphs, the only known previous approximability result is an $O(log n)$-approximation algorithm ($n=|V|$) for $alpha = 1$ by Ding et al. For any constant $alpha > 1$, we give an $O(n^{1-frac{1}{alpha}}(log n)^{frac{1}{alpha}})$-approximation algorithm. When $alpha geq 5$, we give an $O(sqrt{n}log n)$-approximation algorithm. Finally, we prove that, when $alpha =2$, unless $NP subseteq DTIME(n^{polylog n})$, for any constant $epsilon > 0$, the problem admits no polynomial-time $2^{log^{1-epsilon}n}$-approximation algorithm, improving upon the $Omega(log n)$ bound by Du et al. (albeit under a stronger hardness assumption).
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
