Parameterized approximation algorithms for packing problems

DOI10.1016/J.TCS.2016.08.004MaRDI QIDQ313963zbMATHOpenAlexFDO

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

parameterized complexityuniversal sets3-set \(k\)-packing

Mathematics Subject Classification ID

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

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 $alpha$, and a parameter $k$. If the value of an optimal solution is at least $k$, we seek a solution of value at least $alphak$; otherwise, we seek an arbitrary solution. Clearly, if the best known parameterized algorithm that finds a solution of value $t$ runs in time $O^{\ast }(f(t))$ for some function $f$, we are interested in running times better than $O^{\ast }(f(alphak))$. 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."

Recommendations

• An O *(3.523k ) Parameterized Algorithm for 3-Set Packing
• An \(O^{*}(3.53^{3k})\)-time parameterized algorithm for the 3-set packing problem
• Improved Parameterized Algorithms for Weighted 3-Set Packing
• A faster parameterized algorithm for set packing
• Parameterized algorithms for weighted matching and packing problems

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A faster parameterized algorithm for set packing
• A parameterized perspective on packing paths of length two
• An O *(3.523k ) Parameterized Algorithm for 3-Set Packing
• Color-coding
• Combining Two Worlds: Parameterised Approximation for Vertex Cover
• Deterministic algorithms for matching and packing problems based on representative sets
• Efficient computation of representative sets with applications in parameterized and exact algorithms
• Faster Algebraic Algorithms for Path and Packing Problems
• Faster fixed-parameter tractable algorithms for matching and packing problems
• Fundamentals of parameterized complexity
• Greedy Localization and Color-Coding: Improved Matching and Packing Algorithms
• Improved Parameterized Algorithms for Weighted 3-Set Packing
• Improved deterministic algorithms for weighted matching and packing problems
• Iterative Expansion and Color Coding
• Limits and Applications of Group Algebras for Parameterized Problems
• Looking at the stars
• Matching and weighted \(P_2\)-packing: algorithms and kernels
• Mixing Color Coding-Related Techniques
• Narrow sieves for parameterized paths and packings
• Parameterized approximation algorithms for hitting set
• Parameterized approximation via fidelity preserving transformations
• Randomized divide-and-conquer: improved path, matching, and packing algorithms
• Representative families: a unified tradeoff-based approach
• Representative sets of product families
• Using nondeterminism to design efficient deterministic algorithms

Cited in

(13)

• On the Number of Iterations for Dantzig--Wolfe Optimization and Packing-Covering Approximation Algorithms
• Parameterized algorithms for weighted matching and packing problems
• A faster parameterized algorithm for set packing
• Real time asymptotic packing
• Faster fixed-parameter tractable algorithms for matching and packing problems
• Faster deterministic parameterized algorithm for \(k\)-path
• Approximation Algorithms for Demand Strip Packing
• Pseudo-polynomial time algorithms for combinatorial food mixture packing problems
• scientific article; zbMATH DE number 6719727 (Why is no real title available?)
• Approximation algorithms for a hierarchically structured bin packing problem
• scientific article; zbMATH DE number 6850331 (Why is no real title available?)
• Algorithms for packing problems
• Parametric packing of selfish items and the subset sum algorithm

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)