
arXiv: 1505.00709
In the past decade, many parameterized algorithms were developed for packing problems. Our goal is to obtain tradeoffs that improve the running times of these algorithms at the cost of computing approximate solutions. Consider a packing problem for which there is no known algorithm with approximation ratio $��$, and a parameter $k$. If the value of an optimal solution is at least $k$, we seek a solution of value at least $��k$; otherwise, we seek an arbitrary solution. Clearly, if the best known parameterized algorithm that finds a solution of value $t$ runs in time $O^*(f(t))$ for some function $f$, we are interested in running times better than $O^*(f(��k))$. We present tradeoffs between running times and approximation ratios for the $P_2$-Packing, $3$-Set $k$-Packing and $3$-Dimensional $k$-Matching problems. Our tradeoffs are based on combinations of several known results, as well as a computation of "approximate lopsided universal sets."
FOS: Computer and information sciences, universal sets, Combinatorial optimization, Computer Science - Data Structures and Algorithms, Data Structures and Algorithms (cs.DS), 3-set \(k\)-packing, Approximation algorithms, parameterized complexity
FOS: Computer and information sciences, universal sets, Combinatorial optimization, Computer Science - Data Structures and Algorithms, Data Structures and Algorithms (cs.DS), 3-set \(k\)-packing, Approximation algorithms, parameterized complexity
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 1 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
