Campus Event Calendar

Event Entry

What and Who

Faster deterministic algorithms for r-dimensional matching using representative sets

Fahad Panolan
The Institute of Mathematical Sciences, Chennai, India
AG1 Mittagsseminar (own work)
AG 1, AG 2, AG 3, AG 4, AG 5, RG1, SWS, MMCI  
AG Audience

Date, Time and Location

Thursday, 22 August 2013
30 Minutes
E1 4


Given a universe $U := U_1 \uplus \cdots \uplus U_r$, and a $r$-uniform

family $F \subseteq U_1 \times \cdots \times U_r$, the
\textsc{$r$-dimensional matching} problem asks if $F$ admits a collection
of $k$ mutually disjoint sets. The special case when $r=3$ is the classic
{\sc $3$D 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 {\sc
$3$D Matching} problem, a combination of color coding and iterative
expansion yields a running time of $O^*(2.80^{(3k)})$, and for the
\textsc{$r$-dimensional matching} problem, a recently developed
derandomization for known algebraic techniques leads to a running time of

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)k})$ for the {\sc $r$-Dimensional Matching} problem.
Further, we incorporate the principles of iterative expansion used in the
literature [TALG 2012] to obtain a better algorithm for {\sc
$3$D-matching}, 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.


Geevarghese Philip
--email hidden
passcode not visible
logged in users only

Geevarghese Philip, 08/19/2013 10:17 -- Created document.