Header menu link for other important links
X
Faster deterministic algorithms for r-dimensional matching using representative sets
P. Goyal, N. Misra,
Published in Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
2013
Volume: 24
   
Pages: 237 - 248
Abstract
Given a universe U:=U1∪+⋯∪+Ur, and a r-uniform family F ⊆ U1×⋯×Ur, the r-dimensional matching problem asks if F admits a collection of κ mutually disjoint sets. The special case when r = 3 is the classic 3D-Matching problem. Recently, several improvements have been suggested for these (and closely related) problems in the setting of randomized parameterized algorithms. Also, many approaches have evolved for deterministic parameterized algorithms. For instance, for the 3D-Matching problem, a combination of color coding and iterative expansion yields a running time of O∗(2.80(3κ)), and for the r-dimensional matching problem, a recently developed derandomization for known algebraic techniques leads to a running time of O∗(5.44(r-1)κ). In this work, we employ techniques based on dynamic programming and representative families, leading to a deterministic algorithm with running time O∗(2.85(r-1)κ) for the r-Dimensional Matching problem. Further, we incorporate the principles of iterative expansion used in the literature [TALG 2012] to obtain a better algorithm for 3D-matching, with a running time of O∗(2.003(3κ)). Apart from the significantly improved running times, we believe that these algorithms demonstrate an interesting application of representative families in conjunction with more traditional techniques. © Prachi Goyal, Neeldhara Misra, and Fahad Panolan.
About the journal
JournalLeibniz International Proceedings in Informatics, LIPIcs
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISSN18688969