{"@context":["https://w3id.org/fdo/context/v1",{"schema":"https://schema.org/","prov":"http://www.w3.org/ns/prov#","fdo":"https://w3id.org/fdo/vocabulary/"}],"@id":"https://fdo.portal.mardi4nfdi.de/fdo/Q313963","@type":"DigitalObject","kernel":{"@id":"https://fdo.portal.mardi4nfdi.de/fdo/Q313963","digitalObjectType":"https://schema.org/ScholarlyArticle","primaryIdentifier":"mardi:Q313963","kernelVersion":"v1","immutable":true,"modified":"2026-03-23T15:01:52Z"},"profile":{"@context":"https://schema.org","@type":"ScholarlyArticle","@id":"https://portal.mardi4nfdi.de/entity/Q313963","name":"Parameterized approximation algorithms for packing problems","headline":"Parameterized approximation algorithms for packing problems","description":"scientific article; zbMATH DE number 6626484","url":"https://portal.mardi4nfdi.de/entity/Q313963","datePublished":"2016-09-12","author":[{"@id":"https://portal.mardi4nfdi.de/entity/Q249085"}],"publisher":[{"@id":"https://portal.mardi4nfdi.de/entity/Q123643"}],"identifier":{"@type":"PropertyValue","propertyID":"doi","value":"10.1016/J.TCS.2016.08.004","url":"https://doi.org/10.1016/J.TCS.2016.08.004"},"sameAs":["https://doi.org/10.1016/J.TCS.2016.08.004"],"comment":"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)\\).","citation":[{"@id":"https://portal.mardi4nfdi.de/entity/Q3060750"},{"@id":"https://portal.mardi4nfdi.de/entity/Q2896378"},{"@id":"https://portal.mardi4nfdi.de/entity/Q2843261"},{"@id":"https://portal.mardi4nfdi.de/entity/Q4198056"},{"@id":"https://portal.mardi4nfdi.de/entity/Q2396725"},{"@id":"https://portal.mardi4nfdi.de/entity/Q534565"},{"@id":"https://portal.mardi4nfdi.de/entity/Q1882527"},{"@id":"https://portal.mardi4nfdi.de/entity/Q3654388"},{"@id":"https://portal.mardi4nfdi.de/entity/Q958209"},{"@id":"https://portal.mardi4nfdi.de/entity/Q1041711"},{"@id":"https://portal.mardi4nfdi.de/entity/Q3521948"},{"@id":"https://portal.mardi4nfdi.de/entity/Q3499726"},{"@id":"https://portal.mardi4nfdi.de/entity/Q3511321"},{"@id":"https://portal.mardi4nfdi.de/entity/Q3502635"},{"@id":"https://portal.mardi4nfdi.de/entity/Q3195130"},{"@id":"https://portal.mardi4nfdi.de/entity/Q3452864"},{"@id":"https://portal.mardi4nfdi.de/entity/Q393902"},{"@id":"https://portal.mardi4nfdi.de/entity/Q849135"},{"@id":"https://portal.mardi4nfdi.de/entity/Q820158"},{"@id":"https://portal.mardi4nfdi.de/entity/Q3189047"},{"@id":"https://portal.mardi4nfdi.de/entity/Q3638070"},{"@id":"https://portal.mardi4nfdi.de/entity/Q5383969"},{"@id":"https://portal.mardi4nfdi.de/entity/Q2921430"},{"@id":"https://portal.mardi4nfdi.de/entity/Q2921462"},{"@id":"https://portal.mardi4nfdi.de/entity/Q4369883"},{"@id":"https://portal.mardi4nfdi.de/entity/Q383833"}]},"provenance":{"prov:generatedAtTime":"2026-03-23T15:01:52Z","prov:wasAttributedTo":"MaRDI Knowledge Graph"}}