Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userParameterized inapproximability of Morse matching
169
0
0.0
(
0
)
Added by
Abhishek Rathod
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We study the problem of minimizing the number of critical simplices from the point of view of inapproximability and parameterized complexity. We first show inapproximability of Min-Morse Matching within a factor of $2^{log^{(1-epsilon)}n}$. Our second result shows that Min-Morse Matching is ${bf W{[P]}}$-hard with respect to the standard parameter. Next, we show that Min-Morse Matching with standard parameterization has no FPT approximation algorithm for any approximation factor $rho$. The above hardness results are applicable to complexes of dimension $ge 2$. On the positive side, we provide a factor $O(frac{n}{log n})$ approximation algorithm for Min-Morse Matching on $2$-complexes, noting that no such algorithm is known for higher dimensional complexes. Finally, we devise discrete gradients with very few critical simplices for typical instances drawn from a fairly wide range of parameter values of the Costa-Farber model of random complexes.
rate research
Read More
In this paper, we prove that the Max-Morse Matching Problem is approximable, thus resolving an open problem posed by Joswig and Pfetsch. We describe two different approximation algorithms for the Max-Morse Matching Problem. For $D$-dimensional simplicial complexes, we obtain a $frac{(D+1)}{(D^2+D+1)}$-factor approximation ratio using a simple edge reorientation algorithm that removes cycles. Our second result is an algorithm that provides a $frac{2}{D}$-factor approximation for simplicial manifolds by processing the simplices in increasing order of dimension. One application of these algorithms is towards efficient homology computation of simplicial complexes. Experiments using a prototype implementation on several datasets indicate that the algorithm computes near optimal results.
In this paper, we consider the Target Set Selection problem: given a graph and a threshold value $thr(v)$ for any vertex $v$ of the graph, find a minimum size vertex-subset to activate s.t. all the vertices of the graph are activated at the end of the propagation process. A vertex $v$ is activated during the propagation process if at least $thr(v)$ of its neighbors are activated. This problem models several practical issues like faults in distributed networks or word-to-mouth recommendations in social networks. We show that for any functions $f$ and $rho$ this problem cannot be approximated within a factor of $rho(k)$ in $f(k) cdot n^{O(1)}$ time, unless FPT = W[P], even for restricted thresholds (namely constant and majority thresholds). We also study the cardinality constraint maximization and minimizati
Multidimensional packing problems generalize the classical packing problems such as Bin Packing, Multiprocessor Scheduling by allowing the jobs to be $d$-dimensional vectors. While the approximability of the scalar problems is well understood, there has been a significant gap between the approximation algorithms and the hardness results for the multidimensional variants. In this paper, we close this gap by giving almost tight hardness results for these problems. 1. We show that Vector Bin Packing has no polynomial time $Omega( log d)$ factor asymptotic approximation algorithm when $d$ is a large constant, assuming $textsf{P} eq textsf{NP}$. This matches the $ln d + O(1)$ factor approximation algorithms (Chekuri, Khanna SICOMP 2004, Bansal, Caprara, Sviridenko SICOMP 2009, Bansal, Eli{a}s, Khan SODA 2016) upto constants. 2. We show that Vector Scheduling has no polynomial time algorithm with an approximation ratio of $Omegaleft( (log d)^{1-epsilon}right)$ when $d$ is part of the input, assuming $textsf{NP} subseteq textsf{ZPTIME}left( n^{(log n)^{O(1)}}right)$. This almost matches the $Oleft( frac{log d}{log log d}right)$ factor algorithms(Harris, Srinivasan JACM 2019, Im, Kell, Kulkarni, Panigrahi SICOMP 2019). We also show that the problem is NP-hard to approximate within $(log log d)^{omega(1)}$. 3. We show that Vector Bin Covering is NP-hard to approximate within $Omegaleft( frac{log d}{log log d}right)$ when $d$ is part of the input, almost matching the $O(log d)$ factor algorithm (Alon et al., Algorithmica 1998). Previously, no hardness results that grow with $d$ were known for Vector Scheduling and Vector Bin Covering when $d$ is part of the input and for Vector Bin Packing when $d$ is a fixed constant.
A emph{2-interval} is the union of two disjoint intervals on the real line. Two 2-intervals $D_1$ and $D_2$ are emph{disjoint} if their intersection is empty (i.e., no interval of $D_1$ intersects any interval of $D_2$). There can be three different relations between two disjoint 2-intervals; namely, preceding ($<$), nested ($sqsubset$) and crossing ($between$). Two 2-intervals $D_1$ and $D_2$ are called emph{$R$-comparable} for some $Rin{<,sqsubset,between}$, if either $D_1RD_2$ or $D_2RD_1$. A set $mathcal{D}$ of disjoint 2-intervals is $mathcal{R}$-comparable, for some $mathcal{R}subseteq{<,sqsubset,between}$ and $mathcal{R} eqemptyset$, if every pair of 2-intervals in $mathcal{R}$ are $R$-comparable for some $Rinmathcal{R}$. Given a set of 2-intervals and some $mathcal{R}subseteq{<,sqsubset,between}$, the objective of the emph{2-interval pattern problem} is to find a largest subset of 2-intervals that is $mathcal{R}$-comparable. The 2-interval pattern problem is known to be $W[1]$-hard when $|mathcal{R}|=3$ and $NP$-hard when $|mathcal{R}|=2$ (except for $mathcal{R}={<,sqsubset}$, which is solvable in quadratic time). In this paper, we fully settle the parameterized complexity of the problem by showing it to be $W[1]$-hard for both $mathcal{R}={sqsubset,between}$ and $mathcal{R}={<,between}$ (when parameterized by the size of an optimal solution); this answers an open question posed by Vialette [Encyclopedia of Algorithms, 2008].
An $h$-queue layout of a graph $G$ consists of a linear order of its vertices and a partition of its edges into $h$ queues, such that no two independent edges of the same queue nest. The minimum $h$ such that $G$ admits an $h$-queue layout is the queue number of $G$. We present two fixed-parameter tractable algorithms that exploit structural properties of graphs to compute optimal queue layouts. As our first result, we show that deciding whether a graph $G$ has queue number $1$ and computing a corresponding layout is fixed-parameter tractable when parameterized by the treedepth of $G$. Our second result then uses a more restrictive parameter, the vertex cover number, to solve the problem for arbitrary $h$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
