Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userCovering with Clubs: Complexity and Approximability
64
0
0.0
(
0
)
Added by
Florian Sikora
Publication date
2018
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Finding cohesive subgraphs in a network is a well-known problem in graph theory. Several alternative formulations of cohesive subgraph have been proposed, a notable example being $s$-club, which is a subgraph where each vertex is at distance at most $s$ to the others. Here we consider the problem of covering a given graph with the minimum number of $s$-clubs. We study the computational and approximation complexity of this problem, when $s$ is equal to 2 or 3. First, we show that deciding if there exists a cover of a graph with three $2$-clubs is NP-complete, and that deciding if there exists a cover of a graph with two $3$-clubs is NP-complete. Then, we consider the approximation complexity of covering a graph with the minimum number of $2$-clubs and $3$-clubs. We show that, given a graph $G=(V,E)$ to be covered, covering $G$ with the minimum number of $2$-clubs is not approximable within factor $O(|V|^{1/2 -varepsilon})$, for any $varepsilon>0$, and covering $G$ with the minimum number of $3$-clubs is not approximable within factor $O(|V|^{1 -varepsilon})$, for any $varepsilon>0$. On the positive side, we give an approximation algorithm of factor $2|V|^{1/2}log^{3/2} |V|$ for covering a graph with the minimum number of $2$-clubs.
rate research
Read More
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.
A directed odd cycle transversal of a directed graph (digraph) $D$ is a vertex set $S$ that intersects every odd directed cycle of $D$. In the Directed Odd Cycle Transversal (DOCT) problem, the input consists of a digraph $D$ and an integer $k$. The objective is to determine whether there exists a directed odd cycle transversal of $D$ of size at most $k$. In this paper, we settle the parameterized complexity of DOCT when parameterized by the solution size $k$ by showing that DOCT does not admit an algorithm with running time $f(k)n^{O(1)}$ unless FPT = W[1]. On the positive side, we give a factor $2$ fixed parameter tractable (FPT) approximation algorithm for the problem. More precisely, our algorithm takes as input $D$ and $k$, runs in time $2^{O(k^2)}n^{O(1)}$, and either concludes that $D$ does not have a directed odd cycle transversal of size at most $k$, or produces a solution of size at most $2k$. Finally, we provide evidence that there exists $epsilon > 0$ such that DOCT does not admit a factor $(1+epsilon)$ FPT-approximation algorithm.
The bin covering problem asks for covering a maximum number of bins with an online sequence of $n$ items of different sizes in the range $(0,1]$; a bin is said to be covered if it receives items of total size at least 1. We study this problem in the advice setting and provide tight bounds for the size of advice required to achieve optimal solutions. Moreover, we show that any algorithm with advice of size $o(log log n)$ has a competitive ratio of at most 0.5. In other words, advice of size $o(log log n)$ is useless for improving the competitive ratio of 0.5, attainable by an online algorithm without advice. This result highlights a difference between the bin covering and the bin packing problems in the advice model: for the bin packing problem, there are several algorithms with advice of constant size that outperform online algorithms without advice. Furthermore, we show that advice of size $O(log log n)$ is sufficient to achieve a competitive ratio that is arbitrarily close to $0.53bar{3}$ and hence strictly better than the best ratio $0.5$ attainable by purely online algorithms. The technicalities involved in introducing and analyzing this algorithm are quite different from the existing results for the bin packing problem and confirm the different nature of these two problems. Finally, we show that a linear number of bits of advice is necessary to achieve any competitive ratio better than 15/16 for the online bin covering problem.
We study the variant of the Euclidean Traveling Salesman problem where instead of a set of points, we are given a set of lines as input, and the goal is to find the shortest tour that visits each line. The best known upper and lower bounds for the problem in $mathbb{R}^d$, with $dge 3$, are $mathrm{NP}$-hardness and an $O(log^3 n)$-approximation algorithm which is based on a reduction to the group Steiner tree problem. We show that TSP with lines in $mathbb{R}^d$ is APX-hard for any $dge 3$. More generally, this implies that TSP with $k$-dimensional flats does not admit a PTAS for any $1le k leq d-2$ unless $mathrm{P}=mathrm{NP}$, which gives a complete classification of the approximability of these problems, as there are known PTASes for $k=0$ (i.e., points) and $k=d-1$ (hyperplanes). We are able to give a stronger inapproximability factor for $d=O(log n)$ by showing that TSP with lines does not admit a $(2-epsilon)$-approximation in $d$ dimensions under the unique games conjecture. On the positive side, we leverage recent results on restricted variants of the group Steiner tree problem in order to give an $O(log^2 n)$-approximation algorithm for the problem, albeit with a running time of $n^{O(loglog n)}$.
In this paper, we study the lower- and upper-bounded covering (LUC) problem, where we are given a set $P$ of $n$ points, a collection $mathcal{B}$ of balls, and parameters $L$ and $U$. The goal is to find a minimum-sized subset $mathcal{B}subseteq mathcal{B}$ and an assignment of the points in $P$ to $mathcal{B}$, such that each point $pin P$ is assigned to a ball that contains $p$ and for each ball $B_iin mathcal{B}$, at least $L$ and at most $U$ points are assigned to $B_i$. We obtain an LP rounding based constant approximation for LUC by violating the lower and upper bound constraints by small constant factors and expanding the balls by again a small constant factor. Similar results were known before for covering problems with only the upper bound constraint. We also show that with only the lower bound constraint, the above result can be obtained without any lower bound violation. Covering problems have close connections with facility location problems. We note that the known constant-approximation for the corresponding lower- and upper-bounded facility location problem, violates the lower and upper bound constraints by a constant factor.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
