In this talk, we illustrate how nondeterminism can be used conveniently
and effectively in designing efficient deterministic algorithms. In particular,
our method gives an O((5.7 k)^k n) parameterized algorithm for the 3-D matching
problem, which significantly improves the previous
algorithm by Downey, Fellows, and Koblitz. The algorithm can be generalized to
yield an
improved algorithm for the r-D matching problem for any positive integer r.
The method can also be employed in designing deterministic algorithms for other
optimization problems as well.
Co-authored with: J. Chen, D. Friesen, and W. Jia.