Abstract
Given a universe U := U_1 + .... + U_r and a runiform family F
which is a subset of U_1 x .... x U_r, the rdimensional matching
problem asks if F admits a collection of k mutually disjoint sets. The
special case when r=3 is the classic 3Dimensional 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 3Dimensional Matching problem, a combination of color coding and iterative expansion yields a running time of O^*(2.80^{(3k)}), and for the rdimensional matching problem, a recently developed derandomization for known algebraic techniques leads to a running time of O^*(5.44^{(r1)k}).
In this work, we employ techniques based on dynamic programming and
representative families, leading to a deterministic algorithm with running time O^*(2.85^{(r1)k}) for the rDimensional Matching problem. Further, we incorporate the principles of iterative expansion used in the literature [TALG 2012] to obtain a better algorithm for 3Dmatching, with a running time of O^*(2.003^{(3k)}). 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.
BibTeX  Entry
@InProceedings{goyal_et_al:LIPIcs:2013:4376,
author = {Prachi Goyal and Neeldhara Misra and Fahad Panolan},
title = {{Faster Deterministic Algorithms for rDimensional Matching Using Representative Sets}},
booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)},
pages = {237248},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897644},
ISSN = {18688969},
year = {2013},
volume = {24},
editor = {Anil Seth and Nisheeth K. Vishnoi},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2013/4376},
URN = {urn:nbn:de:0030drops43761},
doi = {10.4230/LIPIcs.FSTTCS.2013.237},
annote = {Keywords: 3Dimensional Matching, FixedParameter Algorithms, Iterative Expansion}
}
Keywords: 

3Dimensional Matching, FixedParameter Algorithms, Iterative Expansion 
Seminar: 

IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013) 
Issue Date: 

2013 
Date of publication: 

09.12.2013 