Parameterized approximation algorithms for packing problems

DOI10.1016/J.TCS.2016.08.004MaRDI QIDQ313963zbMATH OpenOpenAlexFDO

Authors Meirav Zehavi

Publication date 12 September 2016

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1505.00709

zbMATH Keywords

3-set \(k\)-packing parameterized complexity universal sets

Mathematics Subject Classification ID

Approximation algorithms (68W25) Combinatorial optimization (90C27)

Abstract: 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

a l p h a

, and a parameter

k

. If the value of an optimal solution is at least

k

, we seek a solution of value at least

a l p h a 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 (a l p h a 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."

Review text

A (maximization) problem is fixed-parameter tractable (FPT) with respect to a parameter \(t\) if it can be solved in time \(O^\ast(f(t))\) for some function \(f\). If the best known polynomial-time approximation algorithm for the problem has approximation ratio \(\beta\), then for any approximation ratio \(\alpha<\beta\), if the value of an optimal solution is at least \(k\), we seek a solution of value at least \(\alpha k\) and we are interested in running times better than \(O^\ast(f(\alpha k))\).NEWLINENEWLINEThe main contribution of this paper is the adaptation of notions fundamental to the representative sets technique to the design of approximation algorithms: The author introduces the definition of ``approximate lopsided universal sets, combining partial executions of representative sets-based algorithms with approximation algorithms, and adapting the iterative expansion framework (in the context of representative sets) to the design of parameterized approximation algorithms. Tradeoffs between \(O^\ast\) running times and approximation ratios are presented in the context of the well-known 3\textsc{-Set} \(k\)\textsc{-Packing}, \(P_2\)\textsc{-Packing} and 3\textsc{-Dimensional} \(k\)\textsc{-Matching} (3D \(k\)\textsc{-Matching}) problems.NEWLINENEWLINEThe following theorem has been proven for the tradeoff version of \(P_2\)\textsc{-Packing} with parameter \(\alpha\):NEWLINENEWLINE\((\alpha, P_2)\)\textsc{-Packing} is solvable in deterministic time \(O^\ast \left(2^{o(k)}\cdot\frac{\binom{3k}{\alpha k}}{\binom{k}{\alpha k}}\right)\).

Recommendations

Cites work

Cited in

(14)

This page was built for publication: Parameterized approximation algorithms for packing problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q313963)