Parameterized approximation algorithms for packing problems

DOI10.1016/J.TCS.2016.08.004zbMATH Open1355.68294arXiv1505.00709OpenAlexW808328477MaRDI QIDQ313963FDOQ313963

Meirav Zehavi

Publication date: 12 September 2016

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

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^{*}(f(t))$ for some function $f$, we are interested in running times better than $O^{*}(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."

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

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

zbMATH Keywords

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

Mathematics Subject Classification ID

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

Cites Work

• Fundamentals of parameterized complexity
• Title not available (Why is that?)
• Efficient Computation of Representative Sets with Applications in Parameterized and Exact Algorithms
• A faster parameterized algorithm for set packing
• Narrow sieves for parameterized paths and packings
• Representative Sets of Product Families
• Representative Families: A Unified Tradeoff-Based Approach
• Mixing Color Coding-Related Techniques
• Faster Algebraic Algorithms for Path and Packing Problems
• Limits and Applications of Group Algebras for Parameterized Problems
• Color-coding
• Looking at the stars
• Randomized divide-and-conquer: improved path, matching, and packing algorithms
• Improved deterministic algorithms for weighted matching and packing problems
• A parameterized perspective on packing paths of length two
• Using nondeterminism to design efficient deterministic algorithms
• Parameterized Approximation via Fidelity Preserving Transformations
• Parameterized Approximation Algorithms for Hitting Set
• Combining Two Worlds: Parameterised Approximation for Vertex Cover
• Iterative Expansion and Color Coding
• Deterministic Algorithms for Matching and Packing Problems Based on Representative Sets
• Greedy Localization and Color-Coding: Improved Matching and Packing Algorithms
• An O *(3.523k ) Parameterized Algorithm for 3-Set Packing
• Improved Parameterized Algorithms for Weighted 3-Set Packing
• Matching and weighted \(P_2\)-packing: algorithms and kernels
• Faster fixed-parameter tractable algorithms for matching and packing problems

Cited In (13)

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

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)