Using Nondeterminism to Design Efficient Deterministic Algorithms

 

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.