ﻻ يوجد ملخص باللغة العربية
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.
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
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
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
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
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$,